§ 1. Наибольший общий делитель

§ 1. Наибольший общий делитель

Откровенно говоря, мы надеемся, что многое в этой главе окажется для вас знакомым.

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

Возьмем некоторую дробь а/b, отношение двух целых положительных чисел а и b. Обычно мы стараемся привести ее к простейшему виду, т. е. мы стараемся сократить множители, общие для а и b.

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

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

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

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

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

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

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

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

а = р₁^?₁ • … • р_r^?_r, b = р₁^?₁ • … • р_r^?_r. (4.1.1)

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

р₁, p₂…, р_r

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

а = 140, b = 110, (4.1.2)

то

а = 2² • 5¹ • 7¹ • 11⁰, b = 2¹ • 5¹ • 7⁰ • 11¹. (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₀. Простыми множителями p_i числа d₀ являются те, которые одновременно встречаются в числах а и b, а степень числа р_i в числе d₀ есть меньшее из двух чисел ?_i и ?_i.

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

d₀ = 2¹ 5¹ = 10.

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

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

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

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

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

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

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