Великая теорема Ферма: история и обзор подходов к доказательству

дипломная работа

§ 1. Предварительные сведения

В этом параграфе напомним основные факты о делимости целых чисел и сравнимости по модулю.

Если a, b Z , b 0, то говорят, что b делит a или a кратно b, если a = bq для некоторого q Z. В этом случае пишут a b или b | a .

Примеры: 1. 156 52, т.к. 148 = 523.

2. -143 52, т.к. -143 = 52(-3) + 13, т.е. -143 даёт остаток 13 при делении на 52.

Упомянем важнейшие свойства делимости нацело:

10. Если a | b и c | d , то ac | bd. В частности, верно a | bc, ac | |bc|, |ac| | bc , (a) | (b) при любой независимой друг от друга расстановке знаков у чисел a и b.

20. Если a | b1 , … , a | bk , то a | (b1c1+ …+bkck ) для любых целых чисел c1 , … , ck .

30. Если a 0, b | a, то |b| |a|. В частности у каждого ненулевого целого числа лишь конечное число делителей.

Пусть a1 , … , an - целые числа, одновременно не равные нулю. Их общим делителем называется любое целое число d, делящее все указанные числа. Наибольший среди всех общих делителей не равных одновременно нулю целых чисел a1 , … , an называется наибольшим общим делителем этих чисел и обозначается через НОД(a1 , … , an) или (a1 , … , an).

Примеры: НОД(0, 8) = 8, (12, 18) = 6, НОД(7, 9) = 1, (12, 40, 28) = 4, НОД(0, 0) не определён.

Общим кратным ненулевых целых чисел a1 , … , an называется любое целое число, делящееся одновременно на каждое из указанных чисел. Наименьшее положительное кратное этих чисел называется их наименьшим общим кратным и обозначаемое символом НОК[a1 , … , an] или просто через [a1 ,… , an].

Примеры: НОК[0, 2] не определено, [24, 16] = 48, НОК[4, 6] = 24, НОК[8, 6, 30] = 120.

В дальнейшем, имея дело с НОД(a1 , … , an) всегда будем молчаливо предполагать, что целые числа a1 , … , an одновременно не равны нулю, а имея дело с НОК[a1 , … , an] - что целые числа все a1 , … , an ненулевые.

Напомним важнейшие свойства наибольшего общего делителя и наименьшего общего кратного:

10. НОД(a1 , … , an) и НОК[a1 , … , an] определёны однозначно.

20. Для произвольной перестановки (i1 , … , in) символов 1, … , n справедливы равенства

НОД(a1 , … , an) = НОД(), НОК[a1 , … , an] = НОК[].

30. Справедливы равенства

НОД(a1 , … , an) = НОД(±a1 , … , ±an), НОК[a1 , … , an] = НОК[±a1 , … , ±an] при любых знаках в правых частях.

40. Если a | b, то НОД(a, b) = |a|, НОК[a, b] = |b|.

50. Для произвольного t Z справедливы равенства

НОД(a, b) = НОД(a, b - at) = НОД(a - bt, b).

60. Любой общий делитель d целых чисел а1 , … , an делит их наибольший общий делитель НОД(a1 , … , an), любое общее кратное K целых чисел а1 , … , an делится на их наименьшее общее кратное НОК[а1 , … , an].

110. Справедливо равенство НОК[a, b] = .

Замечание. Обобщение НОК[a1 , … , аn] = доказанной формулы на случай любого числа сомножителей неверно. Например,

НОК[2, 4, 6] = 12 = 24.

20. Справедливы формулы

(a1 , … , an) = ((a1 , … , an-1), an), [a1 , … , an] = [[a1 , … , an-1], an],

из которых следует, в частности, что вычисление НОД(a1 , … , an) и НОК[a1 , … , аn] сводится к последовательному вычислению аналогичных величин для двух чисел:

(a1 , … , an) = (((…((a1 , a2), a3), … ), an-1), an).

[a1 , … , an] = [[[…[[a1 , a2], a3], … ], an-1], an].

140. Для любого ненулевого с Z верны формулы

НОД(ca1 , … , can) = |c|НОД(a1 , … , an),

НОК[ca1 , … , can] = |c|НОК[a1 , … , an].

Как известно, НОД(a, b) удобно вычислять с помощью алгоритма Евклида.

Примеры: 1. Вычислить НОД(244, 356).

Таким образом, НОД(244, 356) = 4 - последнему ненулевому остатку в алгоритме Евклида.

2. Вычислить НОД(244, 356, 96).

Имеем НОД(244, 356, 96) = ((244, 356), 96) = (4, 96) = 4.

3. Вычислить НОК[35, 50, 20].

Имеем НОК[35, 50, 20] = [[35, 20], 50] = = [140, 50] = = 700, т.к. НОД(35, 20) = 5НОД(7, 4) = 51 = 5 и [140, 50] = 10[14, 5] = = 1070 = 700.

Целые числа a1 , … , an называются взаимно простыми (в совокупности), если НОД(a1 , … , an) = 1. Они называются попарно взаимно простыми в случае, когда НОД(ai , aj) = 1 (1 i < j n).

Примеры: 1. Числа 6, 4, 3 взаимно просты в совокупности, но не попарно.

2. Числа 6, 11, 35 попарно взаимно просты.

3. Два числа взаимно просты в совокупности тогда и только тогда, когда они попарно взаимно просты.

Лемма (основное свойство двух взаимно простых чисел). Если целые числа a, b взаимно просты и a | bc, где с Z, то a | c.

Доказательство. Утверждение очевидно, если a = ±1. В противном случае из НОД(a, b) = 1 получаем, во-первых, b 0 (иначе НОД(a, b) = |a| > 1), а во-вторых, НОК[a, b] = = |ab| . С другой стороны, bc b и bc a, т.е. bc - общее кратное чисел a, b, а значит, по свойства делимости делится нацело на НОК[a, b] = |ab| = ±ab. Таким образом, bc = abq для некоторого целого q, т.е. c = aq и a | c.

Лемма доказана.

Следствие 1. Если целое число a взаимно просто с b1 , … , bn и для некоторого c Z a делит b1…bnc, то a | c.

Доказательство. Постепенно уменьшаем число сомножителей: из условий a | b1…bnc и НОД(a, b1) = 1 следует по лемме a | b2…bnc . Продолжая этот процесс, на некотором шаге получим a | bnc и НОД(a, bn) = 1, откуда по лемме a | c .

Следствие 1 доказано.

Следствие. Целое число взаимно просто с каждым из нескольких целых чисел тогда и только тогда, когда оно взаимно просто с их произведением.

Доказательство. Если целое число a взаимно просто с каждым из нескольких целых чисел b1 , … , bn , и НОД(a, b1…bn) = D, то D взаимно просто с каждым bi (1 i n): любой общий делитель D и bi является общим делителем a и bi , т.е. равен ±1. Поэтому D | b1…bn1, и по следствию 1, D | 1, т.е. D = 1, что и требовалось.

Обратно, если a взаимно просто с b1…bn , то любой общий делитель a и bi будет общим делителем a и b1…bn , т.е. a взаимно просто с bi (1 i n).

Следствие 2 доказано.

Натуральное число p называется простым, если оно имеет ровно два различных натуральных делителя 1 и p.

Примеры: 1. Числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 - простые.

2. Числа -2, 0, 1, 4, 9, 10, 15, - не простые.

Напомним наиболее важные свойства простых чисел.

10. Любые два различных простых числа взаимно просты.

20. Для целого числа a и простого p верно НОД(a, p) > 1 a p.

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

Основная теорема арифметики. Любое целое число n, модуль которого больше 1, единственным образом записывается в виде канонического произведения , где k 1, ± {+ , -}, pi - простые числа, i N и p1 < … < pk .

Пример: Найдём каноническое разложение числа -6230840.

Последовательно делим число n = 6230840 на простые числа:

ni

6230840

3115420

1557710

778855

155771

22253

3179

289

17

pi

2

2

2

5

7

7

11

17

17

Таким образом, 6230840 = 2357211172, а -6230840 = -2357211172. Здесь и далее первые степени простых чисел не пишем.

Следствие (о взаимно простых сомножителях степени). Если имеется разложение nk = m1…ms степени целого числа n в произведение попарно взаимно простых целых ненулевых сомножителей m1 , … , ms , то эти сомножители, с точностью до знака, являются k-ми степенями некоторых попарно взаимно простых чисел. Более точно: mi = iuik , где i {-1, 1}, ui N , НОД(ui , uj) = 1 (1 i s, 1 j s), |n| = u1…us , 1s = .

Доказательство. Запишем mi = i|mi| , где i = 1, если mi > 0 и i = -1, если mi > 0 (1 i s), и аналогично n = |n|. Тогда, очевидно, получается равенство k|n|k = (1s)|m1|…|ms|, откуда = = k = 1s , |n|k = = |m1|…|ms| . При этом все модули являются натуральными числами, так что осталось доказать утверждение для натуральных чисел.

Пусть n, m1 , … , ms N имеют разложения , (1 i s) в произведения простых чисел, где выполнены неравенства p1 < … < pf , а rij - простые числа, не встречающиеся среди p1 , … , pf . Тогда . Переставляя простые числа в правой части (собирая их в степени с одинаковыми основаниями), получим в левой и правой частях равенства канонические разложения, которые должны быть одинаковыми по основной теореме арифметики. Это показывает, что в правой части должны отсутствовать сомножители rij (1 j ti , 1 i s), а показатели степеней при простом числе p в левой и правой частях равны: k = (1 f).

Таким образом, , причём ввиду попарной взаимной простоты чисел m1 , … , ms каждое простое число pi (1 i f) участвует лишь в одном из разложений чисел m1 , … , ms . Поэтому

,

где = 1 + … + s , но на самом деле в этой сумме лишь одно ненулевое слагаемое. Значит, сравнивая показатели степеней при p в левой и правой частях равенства, по основной теореме арифметики заключаем, что каждая степень ij делится на k : ij = kij для некоторого натурального или нулевого ij (1 i s, 1 j f).

Итак,

,

т.е. ui = (1 i s).

Эти числа попарно взаимно просты, т.к. любой общий делитель двух из них ui , uj будет общим делителем взаимно простых чисел mi , mj , а значит, равен ± 1.

Следствие доказано.

Наконец, напомним простейшие сведения из теории сравнений. Два целых числа a, b называются сравнимыми по модулю m Z {0}, если a - b m.

Примеры: 8 2 (mod 3), т.к. 8 - 2 = 32, -27 12 (mod 5), т.к. разность -27 - 12 = -39 не делится нацело на 5.

Упомянем некоторые важнейшие свойства сравнений.

10. Числа a и b сравнимы по модулю m тогда и только тогда, когда они дают одинаковые остатки при делении на m.

20. Условия a b и a 0 (mod b) эквивалентны.

30. Любое целое число a сравнимо само с собой по любому модулю m (рефлексивность отношения сравнимости).

40. Если a b (mod m), то b a (mod m) (симметричность отношения сравнимости).

50. Если a b (mod m) и b с (mod m), то a c (mod m) (транзитивность отношения сравнимости).

60. Если a b (mod m), то для любого целого числа c справедливо

a c b c (mod m) , ac bc (mod m).

70. Если a b (mod m) и c d (mod m), то a c b d (mod m).

80. Если a b (mod m) и c d (mod m), то ac bd (mod m).

90. Если a b (mod m), то для любого натурального k верно сравнение ak bk (mod m).

100. Если целые числа a, b, m делятся нацело на число d Z {0}, то a b (mod m) тогда и только тогда, когда .

110. Если da db (mod m) и НОД(d , m) = 1, то a b (mod m).

Сравнения дают удобный язык для изучения делимости чисел. Связь сравнений с делимостью выявлена в свойстве 20.

Примеры: 1. Вычислить остаток числа a4 - 8a3 + 19 при делении на 23, если известно, что a даёт при делении на 23 остаток 5.

Если a 5 (mod 23), то

a4 - 8a3 + 19 (a2)2 - 8aa2 + 19 22 - 852 + 19

- 402 + (22 + 19) -(-6)2 + 0 12 (mod 23),

т.е. искомым остатком будет 12.

2. Вычислить 18100 + 20 (mod 25).

18100 + 20 (-7)100 - 5 (72)50 - 5 (-1)50 - 5

1 - 5 -4 21 (mod 25).

Таким образом, не вычисляя числа 18100 + 20, можно сказать, что остаток этого числа при делении на 25 равен 21.

3. Найти младшую цифру числа 2435 - 18 .

Нужно вычислить . Имеем

2435 - 18 435 - 8 (42)174 - (-2) 6174 + 2 64 + 2 4 + 2 = 6 (mod 10).

Здесь использован тот факт, что младшая цифра числа 6k равна 6, т.е. 6k 6 (mod 10). Таким образом, искомой младшей цифрой будет 6.

Делись добром ;)