a = d • а1, b = d • b1.

Если число d — общий делитель чисел а и b, то он также делит числа а + b и а — b, так как

а + b = а1d + b1d = (а1 + b1) d,

а — b = а1d — b1d = (а1 — b1) d.

Когда известны разложения чисел а и b на простые множители, нетрудно найти все их общие делители. Выпишем эти два разложения на простые множители:

а = р1α1 • … • рrαr, b = р1β1 • … • рrβr. (4.1.1)

Здесь мы договариваемся записывать разложения чисел а и b так, как если бы они имели одинаковые простые множители

р1, p2…, рr

но с условием, что мы допускаем возможность использования показателя степени, равного 0. Например, если p1 делит число а, но не делит число b, мы полагаем, что в формуле (4.1.1) β1 = 0. Таким образом, если

а = 140, b = 110, (4.1.2)

то

а = 22 • 51 • 71 • 110, b = 21 • 51 • 70 • 111. (4.1.3)

Из формулы (4.1.1) следует, что любой делитель d числа а может иметь простыми множителями только числа pi, которые встречаются в числе а и каждое из них содержится в степени δi, не превосходящей соответствующей степени αi в числе а. Аналогичные условия имеют место и для любого делителя d числа b. Поэтому общий делитель d чисел а и b может иметь в качестве простых множителей только числа pi, которые встречаются одновременно в числах а и b, а степень δi числа pi в d не может превосходить меньшей из двух степеней: αi и βi.

Из этого обсуждения мы можем сделать вывод: любые два натуральных числа а и b имеют наибольший общий делитель d0. Простыми множителями pi числа d0 являются те, которые одновременно встречаются в числах а и b, а степень числа рi в числе d0 есть меньшее из двух чисел αi и βi.

Пример. Возьмем два числа, указанных в (4.1.2), имеющие разложения на простые множители (4.1.3); очевидно, что

d0 = 21 51 = 10.

Так как степень простого числа pi в наибольшем общем делителе по крайней мере не меньше, чем у любого другого общего делителя, то мы получаем характеристическое свойство:

Любой общий делитель d делит наибольший общий делитель d0.

Наибольший общий делитель двух чисел настолько важен, что для него существует специальное обозначение:

d0 = D(a, b). (4.1.4)

Система задач 4.1.

1. Найдите наибольший общий делитель пар чисел: а) 360 и 1970, б) 30 и 365, в) номера вашего телефона и вашего почтового индекса.

2. Как бы вы стали доказывать, что √2 есть иррациональное число, используя в доказательстве теорему о единственности разложения?

Число 1 является общим делителем для любой пары чисел а и b. Может случиться, что единица будет единственным их общим делителем, т. е.

d0 = D(a, b) = 1. (4.2.1)

В этом случае мы говорим, что числа а и b взаимно простые.

Пример. (39, 22) = 1.