Учебник + задачник АП Ильиных

первая строка в (2.4) показывает, что q1 – частное, а r1m – остаток от деления am на bm. Значит (2.4) – алгоритм Евклида для чисел am и bm. Поэтому (am, bm) = rnm. Так как rn = (a, b), то (am, bm) = (a, b)m.

СВОЙСТВО 2. Пусть m – общий делитель чисел a и b. Тогда

a

b

=

a, b

,

( )

.

(2.5)

m

m

m

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

=

a

, b1

=

b

. Тогда a = a1m и

m

m

b = b1m. Требуемое равенство (2.5) переписывается в виде

(a1, b1) =

(a1m, b1m)

,

m

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

ОПРЕДЕЛЕНИЕ 2.3 . Два числа a и b называются взаимно простыми, если их НОД равен единице.

Тем самым

числа a и b взаимно просты (a, b) = 1.

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

ОПРЕДЕЛЕНИЕ 2.4 . Числа 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.

11

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

.		.
.	и	.
1) d1 . d		2) d . d1.

.
.
1) Проверим. d1 . d. Для числа d = (b, c) имеем: d – общий делитель
.
b и c. Тогда ab . d и число d общий делитель чисел ab и c. По замечанию
			.
			.
2.1, стр. 9 получаем, что d делитель числа d1 = (ab, c). Итак, d1 . d.
.
.	. Так как d1	НОД чисел ab и c, то d1	общий делитель
2) Проверим d . d1

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

Получили d ... d1 и d1 ... d, т.е. d = d1, что и нужно.

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

Доказательство. Проверяемое утверждение имеет вид

(a1, c) = 1, (a2, c) = 1, . . . , (an, c) = 1 (a1a2 . . . an, c) = 1.

Так как (a1, c) = 1, то по свойству 4 выполнено равенство

(a1a2 . . . an, c) = (a2 . . . an, c).

Далее

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

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

Доказательство. Нужно доказать, что

ab ... c (a, c) = 1 b ... c.

Так как ab ... c, то (ab, c) = c. По условию (a, c) = 1. Тогда по свойству 4 (ab, c) = (b, c). Поэтому (b, c) = c, откуда b ... c.

12

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

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

ax + by = d.

(3.1)

Запись числа d = (a, b) в виде (3.1) называется линейной формой НОД чисел a и b. Числа x и y – коэффициенты линейной формы.

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

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

a	= bq1 + r1,
b	= r1q2 + r2,
r1	= r2q3 + r3,			(3.2)
. . .
rn−2 = rn−1qn + rn,
rn−1 = rnqn+1.
Этап 2 (подъем вверх). Из		предпоследнего		равенства выразим
rn = d. Получим некоторые x1, y1 Z с условием				(3.3)
rn = rn−2 ·		1 +rn−1(−qn ).
	|{z}1		y1
			|{z}

x

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

rn ` rn−2, rn−1.

(3.4)

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

rn ` rn−3, rn−2.

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

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

13

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

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

"

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

Число c называется общим кратным чисел a и b, если c кратно a и c кратно b.

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

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

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

[a, b] =	ab	.	(3.5)
	(a, b)

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

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

a = a1d и b = b1d.

(3.6)

Числа a1 и b1 получены из чисел a и b делением на их НОД, равный d. По свойству 3 из свойств НОД имеем (a1, b1) = 1. Допустим, что c – общее кратное чисел a и b. Тогда c = aq = bt для некоторых q, t Z. Заменим a и

b на их выражения из (3.6). Получим c = a1dq = b1dt. Тогда a1dq = b1dt и
.								.
.								.
a1q = b1t. Отсюда a1q . b1. C учетом			(a1, b1) = 1 получаем q . b1, т.е. q = b1s.
a1db1d				ab
Тогда c = a1dq = a1db1s =			s =			s. Получили, что любое общее
	d
				d
кратное c чисел a и b выражается в виде					ab		s.
					d			ab
Проверить самостоятельно, что любое число c =									s, где s Z явля- "
								d

ется общим кратным чисел a и b.

14

(3.7)

c = [a, b]s.

Тем самым общие кратные c чисел a и b имеют вид [a, b]s, что и нужно.

Аналогично определению НОК двух чисел можно дать определение НОК нескольких чисел a1, a2, . . . an, где n > 1.

ОПРЕДЕЛЕНИЕ 3.2. Наименьшим общим кратным [a1, a2, . . . , an] чисел a1, a2, . . . , an называется наименьшее из положительных общих кратных этих чисел.

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

на [a, b]. Получим другой вид формулы

этой формуле выражение

Общее кратное c чисел a и b вычисляется по формуле (3.7). Заменим в ab

(a, b)

Наименьшее общее кратное получим при s = 1. Получили формулу (3.5). Теорема доказана.

ЗАМЕЧАНИЕ 3.1 . Число c является общим кратным чисел a и b тогда и только тогда, когда c кратно НОК чисел a и b, т.е.

c ... a c ... b c ... [a, b].

(3.7)

c = (a,abb)s, где s Z.

Итак, получена следующая формула для общих кратных c чисел a и b

a1, a2, . . . , an = [[a1, a2], a3], . . . , an .

(3.8)

Доказательство. Случай n < 3 очевиден. Пусть n = 3. Проверим, что
[a1, a2, a3] = [[a1, a2], a3]. Пусть M – множество общих кратных трех чисел
a1, a2, a3 и M0 – множество общих кратных двух чисел [a1, a2] и a3.
По замечанию 3.1 слова «c кратно чисел a1 и a2» можно заменить
на слова «c кратно числу [a1, a2]». Поэтому M = M0. Тогда совпада-
ют наименьшие положительные числа из этих множеств, т.е. [a1, a2, a3] =
= [[a1, a2], a3].
Случай n > 3 рассмотреть самостоятельно. Теорема доказана.	"

15

Лекция 4. Простые числа.

Произвольное натуральное число a > 1 имеет два тривиальных делителя: 1 и само число a. У некоторых натуральных чисел нет делителей, отличных от тривиальных.

ОПРЕДЕЛЕНИЕ 4.1. Натуральное число a > 1 называется простым числом, если у него нет делителей, отличных от 1 и от самого числа a.

ОПРЕДЕЛЕНИЕ 4.2 . Натуральное число a > 1 называется составным числом, если оно имеет делитель, отличный от 1 и a.

ПРИМЕР. Числа 2, 7, 31 – простые, а числа 4, 12, 28 − 1 – составные. Заметим, что понятие простого и составного числа вводится на множестве чисел > 1. Поэтому число 1 не принадлежит ни к простым числам,

ни к составным.

Понятия простого и составного числа являются отрицанием друг друга. Если известно, что число a > 1 не простое, то делается вывод, что оно составное. Число a > 1, не являющееся составным, – простое число.

Свойства простых чисел.

СВОЙСТВО 1. Пусть p – наименьший делитель среди неединичных делителей числа a > 1. Тогда p – простое число.

Доказательство. Предположим противное. Тогда p – составное число. Поэтому p имеет делитель p1, отличный от 1 и p. Имеем 1 < p1 < p. Так как a ... p и p ... p1, то a ... p1. Получили неединичный делитель p1 числа a, меньший чем p. Противоречие, т.к. p – наименьший делитель среди неединичных делителей числа a. Значит p – простое число.

СВОЙСТВО 2. Пусть p – наименьший делитель среди неединичных делителей составного числа a. Тогда p 6 √a.

Доказательство. По свойству 1 p – простое число. Так как p – делитель числа a, то a = pt. При этом t 6= 1, иначе a = p и a – простое, что не так. Так как t 6= 1 и a = pt, то t – неединичный делитель числа a. Поскольку p – наименьший делитель среди неединичных делителей числа a,

то p 6 t. Домножив обе части этого неравенства на p, получим p2 6 pt. Так как pt = a, то p2 6 a и p 6 √a.

СВОЙСТВО 3. Пусть p – простое число, a – произвольное целое число. Тогда a делится на p или числа a и p взаимно просты.

16

Доказательство. Проверим, что a ... p или (a, p) = 1. Обозначим d = (a, p). Тогда d – делитель простого числа p. Поэтому d = 1 или d = p. Если d = 1, то (a, p) = 1, если d = p, то a ... p.

СВОЙСТВО 4. Если ab ... p и p – простое число, то a ... p или b ... p. Доказательство. Предположим противное, т.е. a 6... p и b 6... p. По свой-

ству 3 (a, p) = 1 и (b, p) = 1. Тогда (ab, p) = 1 ( свойство 5 НОД и взаимно

		.
		.
простых чисел). По условию ab . p. Поэтому (ab, p) = p, противоречие.
Аналогичное утверждение справедливо для нескольких сомножите-
лей, т.е.
.	.
.	.	для некоторого i,	где 1 6 i 6 n.
a1a2 . . . an . p ai . p
			.
			.
СВОЙСТВО 5. Пусть p и q простые числа. Если p . q, то p = q.
Доказательство самостоятельно.			"

ТЕОРЕМА 4.1 ( Евклид, III в. до н. э. ). Простых чисел бесконечно много.

Доказательство. Предположим противное, т.е. простых чисел конечное

число. Пусть
p1, p2, . . . , pn	(4.1)

полный список всех простых чисел.

Составим натуральное число a = p1 p2 . . . pn + 1. Тогда a > 1. Рассмотрим наименьший делитель p среди неединичных делителей числа a. Число p является простым по свойству 1 из свойств простых чисел. Тогда p = pi для некоторого i, так как в списке (4.1) учтены все простые числа.

Из p = pi следует p1p2 . . . pn ... p. Кроме того, a ... p, т.к. мы рассматриваем p – делитель числа a.

Имеем a ... p и p1p2 . . . pn ... p. Тогда a − p1p2 · . . . pn ... p, т.е. 1 ... p. Число 1 имеет только единичный делитель. Поэтому p = 1. Противоречие, т.к. p – неединичный делитель. Следовательно, простых чисел бесконечно много. Теорема доказана.

Решето Эратосфена. Для нахождения множества всех простых чисел из промежутка от 1 до a применяется метод, называемый «решетом Эратосфена». Рассмотрим этот метод.

Выпишем список чисел 2, 3, . . . , a и выберем из них простые числа. Для этого

17

1.Обводим первое число списка (т.е. число 2 ) кружком и вычеркиваем все последующие числа, кратные двум. Находим первое невычеркнутое число – это 3. Обводим его кружком и вычеркиваем все последующие числа, кратные 3. Следующее число первое невычеркнутое число 5. Повторяем действия для 5 и так далее.

2.Если вычеркнуты числа, кратные p и при этом p2 > a, то процесс завершаем.

Тогда искомый список найден, вследствие следующего утверждения.

ТЕОРЕМА 4.2. Числа, оставшиеся в списке невычеркнутыми составляют множество всех простых чисел в промежутке от 1 до a.

Доказательство. Для того, чтобы составить список всех простых чисел в промежутке от 1 до a, мы должны удалить из этого промежутка все составные числа и не не удалять ни одного простого числа.

Заметим, что мы каждый раз вычеркивали числа 6= p и кратные p, т.е. вычеркивали составные числа. Поэтому никакое простое число не будет удалено. Покажем, что все составные числа будут вычеркнуты. Пусть b 6 a, число b составное и b не вычеркнуто. Возьмем наименьший дели-

тель p среди неединичных делителей числа b. По свойствам простых чисел число p простое и p 6 √b. Так как b 6 a, то p 6 √a и p2 6 a.

На каком-то этапе у нас было вычеркивание чисел, кратных p и больших p. Мы должны были вычеркнуть b, как кратное p, а оно у нас не вычеркнуто, противоречие. Теорема доказана.

ПРИМЕР. Составить список простых чисел от 1 до 50.

Решение. Выписываем числа от 2 до 50, и применяем решето Эратосфена. После вычеркивания чисел кратных 11 имеем 112 = 121 > 50, и процесс завершен.

			.......	.......		.......	.		.......	.
			.	. . .		.			.
			. . . .			. .			. .
			. . . .		4	. .		6	. .		8
			. . . .			. .			. .
	.......	.	.......2......... .......3.........			.......5.........			.......7.........
	.
	. .
10	. .		12 13 14			15		16 17 18
	. .
	.....11...........

20 21 22 23 24 25 26 27 28 30 31 32 33 34 35 36 37 38 40 41 42 43 44 45 46 47 48 50

9

19

29

39

49

Ответ [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47].

18

Простые числа Ферма и Мерсенна Простое число a называется числом Ферма, если оно имеет вид 2m + 1. Пусть m имеет нечетный делитель k > 1. Тогда m = kl. Обозначим x = 2l. Рассмотрев равенство xk + 1 = (x + 1)(xk−1 − xk−2 + xk−3 − · · · + 1), получим a – составное число. Поэтому m не имеет нечетных делителей 6= 1, т.е. m вида 2n. Получили, что простые числа Ферма имеют вид

Fn = 22n + 1, где n > 0.

(4.2)

Французский математик П.Ферма предположил в 1650 году, что числа Fn простые для любого n. Действительно, при n = 0, 1, 2, 3, 4 имеем простые числа F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537. Однако Л.Эйлер в 1732 г. обнаружил, что F5 – составное число, а именно,

225 + 1 = 641 · 6700417.

Более того, в настоящее время при n > 5 не известно ни одного простого числа Ферма.

Простые числа вида 2n −1 называются простыми числами Мерсенна в честь французского монаха 17 века М. Мерсенна, который изучал такие числа. Если n – составное, то n = m · k где m, k > 1. Тогда для x = 2m имеем a = xk −1 = (x −1)(xk−1 + xk−2 + · · ·+ 1), т.е. a – составное число. Поэтому простые числа Мерсенна имеет вид

Mn = 2n − 1, где n– простое число .

(4.3)

Очевидно, числа M2 = 3, M3 = 7, M5 = 31, M7 = 127 простые. Также просты числа M13, M17 и M19. В 1772 г. Л.Эйлер установил простоту числа M31, а русский священник-математик И.М.Первушин в 1883 г. – простоту числа M61.

Неизвестно, бесконечно ли множество простых чисел Мерсенна. В настоящий момент (2002г.) число 213.466.917 −1 – наибольшое известное простое число Мерсенна ( это 39 известное число Мерсенна). Оно получено в 2001 г. в рамках проекта GIMPS (Great Internet Mersenne Prime Search) Майклом Камероном. Проект GIMPS, объединяющий огромное число исследователей, любителей теории чисел, затратил 13 000 лет компьютерного времени, чтобы обнаружить это простое число. Более подробные сведения можно найти на сайте http://www.mersenne.org/prime.htm.

19

Лекция 5. Каноническое разложение натурального числа.

ТЕОРЕМА 5.1 . Произвольное натуральное число a > 1 можно представить в виде произведения простых чисел. Это представление однозначно с точностью до порядка сомножителей.

Доказательство. Докажем вначале существование разложения. Рассмотрим наименьший неединичный делитель p1 числа a. Тогда p1 – простое число по свойству 1 из свойств простых чисел.

Имеем a = p1a1. Если a1 = 1, то a = p1 – искомое разложение с одним сомножителем. Пусть a1 6= 1. Рассмотрим наименьший неединичный делитель p2 числа a1. Тогда a1 = p2a2 и a = p1p2a2. При a2 = 1 получим a = p1 · p2 – разложение на два сомножителя. Пусть a2 6= 1.

Продолжим этот процесс. Тогда либо на некотором шаге получим искомое разложение

a = p1 · p2 · p3 · . . . · pm,

(5.1)

либо процесс будет бесконечен. Покажем, что второй случай невозможен. Действительно, в этом случае при любом m имеем неравенства a > p1 · p2 · p3 · . . . · pm > 2m. Это невозможно, т.к. 2m неограниченно возрастает при m = 1, 2, . . ..

Докажем единственность разложения. Пусть наряду с разложением (5.1) имеем другое разложение

a = q1 · q2 · q3 · . . .

· qn.

(5.2)

Проверим, что m = n и после перестановки сомножителей в одном из разложений справедливы равенства p1 = q1, . . . , pm = qm.

Из (5.1) очевидно, что a ... p1. Тогда из (5.2) имеем q1 · q2 · . . . · qn ... p1. По свойству простых чисел 4 по крайней мере один из сомножителей q1, q2, . . . , qn делится на p1. Переставляя эти сомножители считаем, что q1 ... p1. По свойству простых чисел 5 имеем q1 = p1. Приравняем правые части из (5.1) и (5.2) и сократим на p1. Получим p2p3 . . . pm = q2q3 . . . pn. Повторяя рассуждения, имеем p2 = q2, и т.д. Если m = n, то получили единственность разложения, т.к. p1 = q1, p2 = q2, . . . pm = qm после перестановки сомножителей в одном из разложений.

20