Алгоритм нахождения обратного значения по модулю

Помогите понять этот код нахождения обратного значения по модулю $%N$%. Т.е. по сути решается уравнение $%a \ast x=1 \mod N$%. Сначала я понимаю: по алгоритму Евклида записываются множители в $%Q$%. Дальше я лишь знаю, что switch связан с цепными дробями и от них дальше "пляшут". Первый case возвращает $%1$%, если числа не взаимно просты. $%Q$% пересчитываются по формуле $%Q = Q(i) \ast Q(i+1)+Q(i-2)$%. Результат по формуле: $%-1^{(n-1)}*Q($%предпоследнее$%)$%. В коде $%-2$%, т.к. вектор хранит одно "запасное". Если $%-1^{(n-1)}$% положительное понятно. А вот если отрицательное, то почему возвращает $%N-Q($%предпоследнее$%)$%?

int Reverse(int x, int N)
{
    vector<int> Q;

    int NN=N;
    int tmp;
    while(x)
    {
        Q.push_back(NN/x);
        tmp=NN%x;
        NN=x;
        x=tmp;
    }
    switch(Q.size())
    {
        case 1:
            return 1;
        case 2:
            return N-Q[0];
        default:
            Q[1]=Q[1]*Q[0]+1;
            for(int i=2;i<Q.size()-1;i++)
            {
                Q[i]=Q[i]*Q[i-1]+Q[i-2];
            }
            if(Q.size()%2==1)
                return Q[Q.size()-2];
            return N-Q[Q.size()-2];
    }

}