О. ОРЕ - Приглашение в теорию чисел

Эта операция не изменяет значения дроби, например,

24/36 = 8/12 = 2/3.

Общим делителем двух натуральных чисел а и b называется натуральное число d , которое является множителем как числа а , так и числа b , т. е.

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

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

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

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

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

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

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

р 1, p 2…, р r

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

а = 140, b = 110, (4.1.2)

то

а = 2 2 • 5 1 • 7 1 • 11 0, b = 2 1• 5 1• 7 0• 11 1. (4.1.3)

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

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

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

d 0= 2 15 1= 10.

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

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

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

d 0= D ( a, b ). (4.1.4)

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

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

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

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

d 0= D ( a, b ) = 1. (4.2.1)

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

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

Если числа имеют общий делитель, больший единицы, то они также имеют общий простой делитель.

Итак, два числа могут быть взаимно простыми только тогда, когда они не имеют общих простых множителей, поэтому условие (4.2.1) означает, что числа а и b не имеют общих простых множителей, т. е. все их простые множители различны.

Вернемся к началу этой главы, где мы приводили дробь а / b к простейшему виду. Если d 0есть наибольший общий делитель чисел а и b , то мы можем написать

a = a 0 d 0, b = b 0 d 0. (4.2.2)

Тогда

a/b = a 0 d 0 /b 0 d 0= a 0 /b 0. (4.2.3)

В формуле (4.2.2) числа а 0и b 0не могут иметь простых общих множителей, в противном случае числа а и b имели бы общин множитель, больший, чём d 0. Следовательно,

D(a 0, b 0) = 1. (4.2.4)

Это означает, что для второй дроби в формуле (4.2.3) дальнейшее сокращение невозможно.

Одним из часто применяемых свойств взаимно простых чисел является следующее.

Если произведение ab делится на число с, которое взаимно просто с числом b, то число а делится на с.