Подільність, Детальна інформація

1406 = 2 * 646 + 76

114 = 1 * 76 + 38

76 = 2 * 38 + 0

Алгоритм Евкліда можна розширити для знаходження таких цілих чисел x та y, що a * x + b * y = d.

ВХІД: два невід’ємних числа a та b, a і b.

ВИХІД: d = НСД(a, b) та такі цілі числа x та y, що a * x + b * y = d.

void nsdrozsh(int a, int b, int *x, int *y, int *k)

{

int p, q, r, s, m, n;

m = a; n = b; p = 1; q = 0; r = 0; s = 1;

while (m!=0 && n!=0)

{

if (m >= n)

{ m = m - n; p = p - r; q = q - s; }

else

{ n = n - m; r = r - p; s = s - q; }

}

if (m == 0)

{ *k = n; *x = r; *y = s; }

else

{ *k = m; *x = p; *y = q; }

}

Приклад. Розширений алгоритм Евкліда. Обчислення НСД(4864, 3458).

5 76 27 38 114 76 5 27 7 38

1 38 32 45 76 38 27 32 38 45

2 0 91 128 38 0 32 91 45 128



Результат: НСД(4864, 3458) = 38, при цьому 4864 * 32 + 3458 * (-45) = 38.

Для обчислення найменшого спільного кратного (НСК) можна використати формулу:

a * b = НСД(a, b) * НСК(a, b).