Skip to main content

Розширений алгоритм Евкліда

Порівнюючи із "звичайним" алгоритмом Евкліда, який знаходить найбільший спільний дільник двох чисел aa і bb, розширений алгоритм Евкліда знаходить, крім НСД, також такі коефіцієнти xx та yy, що:

a⋅x+b⋅y=gcd(a,b).a \cdot x + b \cdot y = {\rm gcd} (a, b).

тобто він знаходить коефіцієнти, за допомогою яких НСД двох чисел виражається через самі ці числа.

Алгоритм​

Введемо обчислення цих коефіцієнтів в алгоритм Евкліда. Для цього достатньо вивести формули, по яким вони змінюються при переході від пари (a,b)(a,b) до пари (b mod a,a)(b\ {\rm mod}\ a, a).

Отже, нехай ми знайшли розв'язок (x1,y1)(x_1,y_1) для задачі з новою парою (b mod a,a)(b\ {\rm mod}\ a,a):

(b mod a)⋅x1+a⋅y1=g,(b\ {\rm mod}\ a) \cdot x_1 + a \cdot y_1 = g,

і хочемо отримати розв'язок (x,y)(x,y) для задачі з парою (a,b)(a,b):

a⋅x+b⋅y=g.a \cdot x + b \cdot y = g.

Для цього перетворимо величину b mod ab\ {\rm mod}\ a наступним чином:

b mod a=b−⌊ba⌋⋅a.b\ {\rm mod}\ a = b - \left\lfloor \frac{b}{a} \right\rfloor \cdot a.

Підставимо у вираз з x1x_1 та y1y_1 і отримаємо:

g=(b mod a)⋅x1+a⋅y1=(b−⌊ba⌋⋅a)⋅x1+a⋅y1,g = (b\ {\rm mod}\ a) \cdot x_1 + a \cdot y_1 = \left( b - \left\lfloor \frac{b}{a} \right\rfloor \cdot a \right) \cdot x_1 + a \cdot y_1,

і, виконавши перегрупування доданків, отримуємо:

g=b⋅x1+a⋅(y1−⌊ba⌋⋅x1).g = b \cdot x_1 + a \cdot \left( y_1 - \left\lfloor \frac{b}{a} \right\rfloor \cdot x_1 \right).

Порівнявши результат з початковим виразом з невідомими xx та yy, отримуємо необхідні рівності:

{x=y1−⌊ba⌋⋅x1,y=x1.\begin{cases} x = y_1 - \left\lfloor \frac{b}{a} \right\rfloor \cdot x_1, \cr y = x_1. \end{cases}

Реалізація​

int gcd(int a, int b, int& x, int& y) {
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    int x1, y1;
    int d = gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

Це рекурсивна функція як і раніше повертає значення НСД від чисел aa та bb, але крім цього також шукані коефіцієнти xx та yy у вигляді параметрів функції, що передаються у вигляді посилань.

База рекурсії a=0a = 0. Значить НСД рівний bb, і, очевидно, необхідні коефіцієнти xx та yy рівні 00 та 11 відповідно. В інших випадках коефіцієнти перераховуються по вищеописаним формулами.

Розширений алгоритм Евкліда у такій реалізації працює правильно навіть для від'ємних чисел.

Застосування​

TODO: add applications

Задачі​