Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2001/01/35.pdf Дата изменения: Fri Dec 23 19:26:13 2005 Дата индексирования: Tue Oct 2 00:13:20 2012 Кодировка: Windows-1251 Поисковые слова: п п п п р п р п р п р п р п р п р п р п

МАТЕМАТИЧЕСКИЙ К МАТЕМАТИЧЕСКИЙ Р У Ж О К КРУЖОК

35

Девятнадцать доказательств теоремы Евклида
А.ЭВНИН
обладают удивительной привлекательностью: математики не устают в течение многих лет находить все новые и новые их доказательства. Известно более 350 различных доказательств теоремы Пифагора. Многие из них собраны в книге [1], в предисловии к которой ее автор пишет: 'Мы хотели показать на простом примере, впрочем имеющем выдающееся значение как с точки зрения истории математики, так и ее преподавания, как разнообразно могут соприкасаться разные области математики, как тесно бывают сплетены математические факты, образуя не цепь, но сеть'. Эти слова в полной мере описывают и цель данной статьи, посвященной теореме, которая моложе теоремы Пифагора на 200 лет и была сформулирована и доказана древнегреческим математиком Евклидом в его знаменитой книге 'Начала'. Теорема. Множество простых чисел бесконечно. Мы приглашаем читателя познакомиться с коллекцией доказательств теоремы Евклида. Большинство из них вполне элементарны. Для понимания некоторых требуется знание начальных понятий теории числовых рядов. Для того чтобы разобраться в топологическом доказательстве, разумеется, нужно знать определение топологического пространства. Основными источниками при написании статьи послужили книги [3], [4], [5], а также страница в Интернете [7]. Начнем с классического (авторского!) доказательства. 1 (Евклид, III в. до н.э.). Предположим, что множество простых чисел конечно и р самое большое простое число. Рассмотрим число k, которое больше произведения всех простых

любого n N имеет место равенство

a

n +1

= a1 a2 K a

n -1

an + 1 .

(1)

База индукции тривиальна. Индукционный шаг. Соотношение 2 ak + 2 = a1a2 ak ak +1 + 1 = ak +1 ak +1 + + 1 равносильно тому, что a1a2 K ak = = ak +1 1. Из (1) следует, что каждый член последовательности Сильвестра взаимно прост со всеми предыдущими. R 4 (Гольдбах). Пусть an = 2 + 1. Докажем, что любые два числа последовательности
2
n

С

УЩЕСТВУЮТ ТЕОРЕМЫ, КОТОРЫЕ

чисел на единицу:

3, 5,17,K, 2
просты.1

2

n

+ 1, K

k = 2 3 5 K p + 1.
Число k не имеет простых делителей, так как при делении на любое простое число дает в остатке 1. Между тем, легко проверить, что наименьший делитель m > 1 натурального числа k, большего 1, является простым числом. Полученное противоречие доказывает теорему. R 2 (Куммер). Суть доказательства Евклида состоит в том, что в предположении конечности множества простых чисел строится некоторое число k, которое не делится ни на одно из простых чисел. Немецкий математик Куммер поменял в рассуждении Евклида лишь один знак, определив число k так: k = 2 3 5 K p - 1 . От взаимно простых чисел к простым Доказательства, собранные в этом разделе, опираются на следующую простую лемму. Лемма 1. Если существует бесконечная последовательность попарно взаимно простых чисел, то множество простых чисел бесконечно. Действительно, у взаимно простых чисел нет общих простых делителей. Поэтому, взяв по одному простому делителю членов упомянутой последовательности, мы получим некоторое бесконечное множество, все элементы которого суть простые числа. R Теперь дело за тем, чтобы найти бесконечные последовательности попарно взаимно простых чисел. 3 (Сильвестр). Рассмотрим последовательность an , определяемую со2 отношениями a1 = 2, ak +1 = ak ak + +1, k N . Вот первые несколько членов этой последовательности: 2, 3, 7, 43. Докажем по индукции, что для

взаимно Ведя доказательство от противного, предположим, что числа an и ak , где n > k, не являются взаимно простыми, т.е. имеют некоторый общий множитель d > 1. Заметим, что рассматриваемая последовательность состоит из нечетных чисел, поэтому d > 2. Применим теперь легко проверяемое тождество

Оно показывает, что число an 2 = n 2 = 2 1 делится на ak , а заодно и на d. Тогда и 2 = an an - 2 делится на d, что невозможно. R 5. Укажем общую конструкцию, частными случаями которой являются последовательности из двух предыдущих доказательств. Пусть а и b взаимно простые числа. Определим последовательность an следующим образом: a1 = а, ak +1 = = a1a2 K ak + b. Отметим, что последовательности из двух предыдущих доказательств получаются при а = 2, b = =1 и а = 1, b = 2 соответственно. Докажем, что любые два элемента последовательности an взаимно простые числа. Заметим сначала, что при n > k число an b = a1a2 K an -1 делится на ak (обозначают: an b M ak ). Пусть d общий делитель чисел an и ak . Из того, что an M d и an b M ak M d , следует b M d .

b1 + 2ge1 + 2 jFH1 + 2 IK Ч F1 + 2 I K F1 + H KH
2 2
2

Ч 2
2
n -1

2

3

I K

=2

2

n

- 1.

c

h

ch

ch

ch

1 Числа данной последовательности называются числами Ферма, который заметил, что эти числа при n = 0, 1, 2, 3, 4 являются простыми, и предположил, что то же будет верно для любого значения n, в чем сильно ошибся: уже a5 составное число. Более того, в настоящее время неизвестно ни одно число Ферма при n > 4, являющееся простым.