Учебник по теории чисел Ильиных АП

условий для остатков r1, r2, . . . , rn.
a = bq1 + r1,	0 6 r1 < b
b = r1q2 + r2,	0 6 r2 < r1
r1 = r2q3 + r3,	0 6 r3 < r2	(1)
. . .	. . .
rn−3 = rn−2qn−1 + rn−1, 0 6 rn−1 < rn−2
rn−2 = rn−1qn + rn,	0 6 rn < rn−1
rn−1 = rnqn+1

Заметим, что на некотором этапе получается остаток rn+1, равный нулю, и поэтому процесс деления обрывается. В противном случае имели бы бесконечную последовательность неравенств b > r1 > r2 > r3 > . . . в которой все числа целые и неотрицательны, а b — фиксированное число, противоречие.

Итак, rn+1 = 0, т.е. rn — последний, не равный нулю остаток.

ТЕОРЕМА 1 Последний, не равный нулю остаток rn в алгоритме Евклида является наибольшим общим делителем чисел a и b.

Доказательство. Проверим, что (a, b) = rn. Применим лемму 2. Имеем (a, b) = (b, r1) = (r1, r2) = (r2, r3) = · · · = (rn−2, rn−1) = (rn−1, rn) = rn. При этом rn−1 ... rn и (rn−1, rn) = rn по свойству 1. Теорема доказана.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

ЗАМЕЧАНИЕ 1 Множество общих делителей чисел совпадает с множество делителей их НОД. Поэтому число c — общий делитель двух чисел a и b тогда и только тогда, когда c — делитель одного числа d = (a, b).

Доказательство. Как и выше применим лемму 2. Имеем Da,b = Db,r1 = Dr1,r2 =

· · · = Drn−1,rn = Drn.

НОД нескольких чисел. Наибольшим общим делителем чисел a1, a2, . . . , an называется наибольший из общих делителей этих чисел. НОД чисел a1, a2, . . . , an обозначается через (a1, a2, . . . , an) .

Для нахождения НОД чисел a1, a2, . . . , an нужно вначале найти НОД d = (a1, a2) чисел a1, a2, а затем НОД d1 = (d, a3), НОД d2 = (d1, a4) и т.д. Это правило дает следующая теорема.

ТЕОРЕМА 2 Справедлива следующая формула для НОД нескольких чи-

сел	, . . . , an .
(a1, a2, . . . , an) = (a1, a2), a3		(2)

Доказательство. Проверим вначале, что (a1, a2, a3) = (a1, a2), a3 . Рассмотрим D — множество общих делителей трех чисел (a1, a2, a3) и D0 — множество общих делителей двух чисел: числа d = (a1, a2) и числа a3. По замечанию

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

1 слова «с —общий делитель чисел a1 и a2» можно заменить на «с — делитель числа d = (a1, a2)».

Поэтому слова «с —общий делитель чисел a1, a2, a3» можно заменить на «с

— общий делитель двух чисел d и a3». Отсюда D = D0. Так как множества D и D0 равны, то равны и наибольшие элементы из этих множеств, т.е. (a1, a2, a3) =

		n > 3
	(a1, a2), a3 .
	Доказательство для случая		аналогично. Теорема доказана.

Свойства НОД и взаимно простых чисел. Рассмотрим свойства наибольшего общего делителя.

СВОЙСТВО 1. Для любых чисел a, b, m справедливо равенство

(am, bm) = (a, b)m.

(3)

Тем самым общий множитель m можно выносить за знак НОД. Доказательство. Найдем НОД чисел a и b с помощью алгоритма Евклида

(1). Для последнего, не равного нулю остатка rn имеем rn = (a, b). Умножим

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

строки из (1) на m. Получим
am	= (bm)q1 + r1m, 0 6 r1m < bm
bm	= (r1m)q2 + r2m, 0 6 r2m < r1m
r1m	= (r2m)q3 + r3m, 0 6 r3m < r2m
. . .	. . .	(4)
rn−3m	= (rn−2m)qn−1 + rn−1, 0 6 rn−1m < rn−2m
rn−2m	= (rn−1m)qn + rn,	0 6 rnm < rn−1m
rn−1m	= (rnm)qn+1

Неравенства, приведенные выше, — это признаки остатка. В частности, первое строка в (4) показывает, что q1 - частное, а r1m — остаток от деления am на bm. Значит (4) — алгоритм Евклида для чисел am и bm и (am, bm) = rnm. Так как rn = (a, b), то (am, bm) = (a, b)m.

СВОЙСТВО 2. Пусть m — произвольный общий делитель чисел a и b. Тогда

a

b

a, b

,

=

( )

.

(5)

m

m

m

Доказательство. Обозначим

a

= a1,

b

= b1. Тогда a = a1m,

b = b1m.

m

m

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

(a1, b1) =

Вместо (5) получаем

(a1m, b1m), m

т.е. (a1, b1)m = (a1m, b1m). Это равенство верно по свойству 1.

Взаимно простые числа. Два числа a и b называются взаимно простыми, если их НОД равен единице.

Аналогично, числа a1, a2, . . . , an взаимно просты, если их НОД равен единице.

Числа a1, a2, . . . , an называются попарно взаимно простыми, если (ai, aj) = 1 при i 6= j.

Пример. Числа 14 и 9 взаимно просты, т.к. (14, 9) = 1, числа 14 и 22 не взаимно просты, т.к.(14, 22) = 2.

Числа 12, 9, 14 взаимно просты, но не попарно взаимно просты.

СВОЙСТВО 3. Если числа a и b разделить на их НОД, то получатся взаимно простые числа.

Доказательство. Обозначим m = (a, b). По свойству 2

ma , mb = (a,mb) = ((a,a, bb)) = 1.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

СВОЙСТВО 4. Пусть числа a и c взаимно просты. Тогда (ab, c) = (b, c). Доказательство. Обозначим d = (b, c) и d1 = (ab, c). Нужно проверить, что

d= d1. Для этого установим, что d1 ... d и d ... d1. Тогда d = d1. Рассмотрим число

d= (b, c).

Так как число d — НОД чисел b и c, то d — общий делитель b и c. Тогда ab ... d и число d общий делитель чисел ab и c. По замечанию 1 d делитель НОД чисел ab и c, т.е. d является делителем числа d1.

Число d1 НОД чисел ab и c и, поэтому, общий делитель чисел ab и c. Тогда d1 общий делитель чисел ab и ac. Поэтому d1 делитель НОД чисел ab и cb, т.е. делитель числа (ab, cb) = (a, c)b = b (с учетом (a, c) = 1 ). Получили, что d1 общий делитель чисел b и c. Тогда d делитель числа d1 = (b, c). Итак, d ... d1 и d1 ... d, откуда d = d1.

СВОЙСТВО 5. Пусть каждое из чисел a1, a2, . . . , an взаимно просто с числом c. Тогда произведение a1a2 . . . an взаимно просто с числом c. Доказательство. Так как (a1, c) = 1, то по свойству 4 (a1a2 . . . an, c) = (a2 . . . an, c). Далее

(a2 . . . an, c) = (a3 . . . an, c) = · · · = (an, c) = 1.

СВОЙСТВО 6. Пусть произведение двух чисел ab делится на c и сомножитель a взаимно прост с числом . Тогда другой сомножитель b делится на c.

Доказательство. Так как ab делится на c, то (ab, c) = c. По условию (a, c) =

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

1. По свойству 4 (ab, c) = (b, c). Поэтому (b, c) = c, откуда b ... c.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Лекция 3. Линейная форма НОД. НОК и его свойства.

Пусть d наибольший общий делитель чисел a и b. Предположим, что мы нашли целые числа x и y такие, что

ax + by = d.

(1)

Запись числа d = (a, b) в виде (1) называется линейной формой НОД чисел a и b.

Cпособ нахождения линейной формы состоит из двух этапов.

Этап 1 (спуск вниз). С помощью алгоритма Евклида найдем d = (a, b). Получим

a = bq1 + r1 b = r1q2 + r2

r1 = r2q3 + r3 (2)

. . .

rn−2 = rn−1qn + rn rn−1 = rnqn+1

Этап 2 (подъем вверх). Из предпоследнего равенства выразим rn. Получим

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

некоторые x1, y1 Z с условием		(3)
rn = rn−2 · 1	+rn−1(−qn ).
|{z}	y1
x1	|{z}

То, что число с выражаем через a и b в виде c = xa + yb, где x, y, Z, записываем c ` a, b. Из (3) имеем

rn ` rn−2, rn−3.

Из следующего вверх равенства выразим rn−1 на его выражение через rn−2, rn−3. Получим

rn ` rn−3, rn−2.

(4)

` rn−2, rn−3. Заменим rn−1 в (3)

Подымаясь вверх, выражая правые части равенств из (2) и подставляя в выражение для rn, на последнем шаге получим rn = xa+ yb для некоторых целых коэффициентов x и y.

С помощью линейной формы легко получить критерий взаимной простоты чисел a и b.

ТЕОРЕМА 1 Числа a и b взаимно просты тогда и только тогда, когда существуют целые числа x и y такие, что ax + by = 1.

Доказательство самостоятельно.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Наименьшее общее кратное. Если a делится на b, то будем говорить, что b кратно a. Число c называется общим кратным чисел a и b, если c кратно a и c кратно b. Наряду с положительным кратным c чисел a и b, отрицательное число −c также кратно a и b. В дальнейшем будем говорить лишь о положительных кратных.

ОПРЕДЕЛЕНИЕ 1 Наименьшим общим кратным ( НОК ) чисел a и b называется наименьшее из положительных общих кратных чисел a и b.

Наименьшее общее кратное чисел a и b обозначается через [a, b].

ТЕОРЕМА 2 Наименьшее общее кратное чисел a и b вычисляется по

	формуле	ab
	[a, b] =		.	(5)
		(a, b)

Доказательство. Выведем вначале формулу для общих кратных и по ней выберем наименьшее из общих кратных.

Обозначим d = (a, b). Тогда
a = a1d и b = b1d.	(6)

При этом (a1, b1) = 1 по свойству 3.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход