Таблицы Брадиса

Тогда на предпоследнем шаге НОДа,

Тогда на предпоследнем шаге НОДа,

Элементы математики в задачах - Г. А. Мерзон

Задача 11. Покажите, как при помощи алгоритма Евклида можно по произвольным а и Ъ найти такие к и I, что ак + Ъ1 = НОД(а, Ъ).

Набросок решения. Выполняя алгоритм Евклида, будем представлять каждое возникающее при этом число в виде ак + Ъ1. Тогда на пред­последнем шаге НОД(а, Ъ) окажется представленным в этом виде. Продемострируем это на примере а = 147, Ъ = 91:

(147,91)

147 =

 

 

147'

1 + 91 ■

 

91 =

 

 

147'

0 + 91 ■

(91,56)

56 =

= 147

— 91 =

147'

1 — 91 ■

(56,35)

35 =

91 —

56 =

— 147'

1 + 91 ■

(35,21)

21 =

= 56 —

35 =

147'

■2 — 91 ■

(21,14)

14 =

= 35 —

21 =

— 147'

■3 + 91 ■

(14,7)

7=

21 —

14 =

147'

■5 — 91 ■

(7,0)

0=

= 14 —

2 ■ 7 =

— 147'

13 + 91

.• 21

 

Целые числа 2. Алгоритм Евклида                167

Задача 12. Докажите, что уравнение ах + Ъу = <і имеет решение в целых числах тогда и только тогда, когда <і. НОД (а, Ъ). В частности,

НОД(а, Ъ) — это наименьшее натуральное число, представимое в ви­де ах + Ъу.

Решение. (^) Пусть уравнение ах + Ъу = d имеет решение в целых числах. Но тогда правая часть делится на НОД (а, Ъ), а значит, должна делиться и левая. То есть d . НОД (а, Ъ).

(^) Пусть d. НОД(а, Ъ), т. е. т НОД(а, Ъ) = d. В силу предыдущей задачи существуют такие целые числа к0 и 10, что ак0 + Ъ10 = НОД (а, Ъ).

Тогда х = к0т, у = 10т —решение уравнения ах + Ъу = d.

Задача 13. Даны углы в 32° и 25°. Постройте угол в 1°.

Решение. Воспользовавшись задачей 11, найдем целые числа к и I, для которых 32к + 25? = 1: 7 = 32 — 25, 4 = 25 — 3 ■ 7 = 4 ■ 25 — 3 ■ 32,

3  = 7 — 4 = 4 ■ 32 — 5 ■ 25, 1 = 4 — 3 = 9 ■ 25 — 7 ■ 32. Таким образом, достаточно отложить от некоторого луча девять раз угол в 25° против часовой стрелки, а от получившегося луча отложить семь раз угол в 32° по часовой стрелке.