§ 1. Наибольший общий делитель
Откровенно говоря, мы надеемся, что многое в этой главе окажется для вас знакомым.
В ней рассматриваются понятия, с которыми вы познакомились в школе, как только научились обращаться с обыкновенными дробями. Единственным оправданием включения этого материала является желание освежить его в вашей памяти. Мы также надеемся, что приведенное изложение материала явится более систематическим, чем то, к которому вы привыкли.
Возьмем некоторую дробь а/b, отношение двух целых положительных чисел а и b. Обычно мы стараемся привести ее к простейшему виду, т. е. мы стараемся сократить множители, общие для а и b.
Эта операция не изменяет значения дроби, например,
24/36 = 8/12 = 2/3.
Общим делителем двух натуральных чисел а и b называется натуральное число d, которое является множителем как числа а, так и числа b, т. е.
a = d • а>1, b = d • b>1.
Если число d — общий делитель чисел а и b, то он также делит числа а + b и а — b, так как
а + b = а>1d + b>1d = (а>1 + b>1) d,
а — b = а>1d — b>1d = (а>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 есть меньшее из двух чисел α
