218. С помощью алгоритма Евклида найдите НОД чисел a и b: а) a = 5075, b = 22 127; б) a = 16 027, b = 160 787.

а) Применим алгоритм Евклида:

22 127 = 5 075 · 4 + 1 827;
5 075 = 1 827 · 2 + 1 421;
1 827 = 1 421 · 1 + 406;
1 421 = 406 · 3 + 203;
406 = 203 · 2.

Последний ненулевой остаток — 203, значит, НОД(5 075, 22 127) = 203.

б) 160 787 = 16 027 · 10 + 517;
16 027 = 517 · 31.

Последний ненулевой остаток — 517, значит, НОД(16 027, 160 787) = 517.

Ответ: а) 203; б) 517.