207. С помощью алгоритма Евклида найдите НОД чисел a и b: а) a = 143, b = 247; б) a = 187, b = 319; в) a = 451, b = 533; г) a = 307, b = 945; д) a = 391, b = 867; е) a = 2581, b = 4005.

а) 247 = 143 · 1 + 104; 143 = 104 · 1 + 39; 104 = 39 · 2 + 26; 39 = 26 · 1 + 13; 26 = 13 · 2. Последний ненулевой остаток — 13, значит, НОД(143, 247) = 13.

б) 319 = 187 · 1 + 132; 187 = 132 · 1 + 55; 132 = 55 · 2 + 22; 55 = 22 · 2 + 11; 22 = 11 · 2. Значит, НОД(187, 319) = 11.

в) 533 = 451 · 1 + 82; 451 = 82 · 5 + 41; 82 = 41 · 2. Значит, НОД(451, 533) = 41.

г) 945 = 307 · 3 + 24; 307 = 24 · 12 + 19; 24 = 19 · 1 + 5; 19 = 5 · 3 + 4; 5 = 4 · 1 + 1; 4 = 1 · 4. Значит, НОД(307, 945) = 1.

д) 867 = 391 · 2 + 85; 391 = 85 · 4 + 51; 85 = 51 · 1 + 34; 51 = 34 · 1 + 17; 34 = 17 · 2. Значит, НОД(391, 867) = 17.

е) 4005 = 2581 · 1 + 1424; 2581 = 1424 · 1 + 1157; 1424 = 1157 · 1 + 267; 1157 = 267 · 4 + 89; 267 = 89 · 3. Значит, НОД(2581, 4005) = 89.

Ответ: а) 13; б) 11; в) 41; г) 1; д) 17; е) 89.