Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2001/01/kv0101evnin.pdf Дата изменения: Fri Dec 23 19:26:09 2005 Дата индексирования: Tue Oct 2 00:33:41 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, являющееся простым.


36
Вновь применим индукцию. База ее очевидна. Предположим, что a1 , a2 , , ak попарно взаимно простые числа. Пусть d > 1 произвольный делитель числа ak +1 . Докажем, что d не является делителем чисел a1 , a2 , , ak . Рассуждая от противного, обозначим через i наименьшее число, для которого ai M d . Если i > 1, то ai = aa2 K ai 1 + b M d 1 и, поскольку b M d , произведение a1 a2 K ai -1 также делится на d, что противоречит взаимной простоте числа ai с предшествующими членами последовательности. Если же i = 1, то a1 = а делится на d, что вновь приводит к противоречию (а и b взаимно простые числа). 6. Обобщить конструкцию Сильвестра можно и по-другому. Пусть a1 = = a 2 , ak +1 = 1 + ak ak - 1 bk , где bn произвольная последовательность натуральных чисел. Заметим, что последовательность Сильвестра получается, если положить а = 2, bn = 1. Одна из задач XII Всесоюзной олимпиады в 1978 году была следующей: Пусть f x = x 3 х + 1, а > 1 натуральное число. Докажите, что числа бесконечной последовательности а, f a , f f a , f f f a , попарно взаимно просты. Нетрудно видеть, что если в нашей конструкции взять bk = ak + 1, то возникнет указанная последовательность. Докажем, что последовательность an состоит из попарно взаимно простых чисел. Действительно, если m > > k, то
b

КВАНT 2001/?1

k 1. Последнее утверждение легко q bq b доказать: k a 1 = k 1 = k 1 b делится на k 1. Пусть теперь а не делится на b, т.е. а = bq + r, 0 < r < b. Имеем: k a 1 = r bq r = k bq + r 1 = k k - 1 + k 1. Как показано выше, k bq 1 делится на kb 1. Кроме того, 0 < k r 1 < k b 1. Таким образом, остаток от деления b a r k 1 на k 1 равен k 1. Поэтому a b b r k - 1, k - 1 = k - 1, k - 1 . Используя соотношения алгоритма Евклида а = bq0 + r1 , b = rq1 + r2 , r1 = 1 = r2 q2 + r3 , , rn -2 = rn -1 qn-1 + rn , rn -1 = = qn rn , получаем цепочку равенств

ej

=2

2

n -1

. Получим
2
n +1

a

n +1

=2
2
n

+2

2

n

+1 =

e

j

=2

F H

+1-2

2

n -1

e e

je j
=

j

Таким образом, a
2
n

IF2 KH F =2 H
n +1

2

n

+1+2
n

2

n -1

2

+1-2
2
n

2

n -1

k - 1, k - 1

a

b

ch

c

h

= k - 1, k - 1 = = k
rn

bg

=k 1=k 1. Сопоставляя начало и конец этой цепочки, получаем требуемое. Следствие. Если m и n взаимно просты, то взаимно простыми будут и числа 2m 1 и 2n 1. Действительно, если m, n = 1, то m n b m,ng 1 = 21 1 = 1. 2 - 1, 2 - 1 = 2 7 (Холщинский, 1994). Предположим, что F = n1 , n2 , K, nk множество всех простых чисел ( n1 = 2, n2 = 3, n3 = 5, ). Очевидно, что числа из F попарно взаимно просты; в силу следn ствия леммы 2 при i j числа 2 i 1 nj и 2 1 также взаимно просты. Выберем теперь для каждого i = 1, 2, , k какой-нибудь простой делитель pi n числа 2 i 1; числа p1 , p2 , , pk будут попарно различны. В результате образуется множество G = = p1 , p2 , K, pk простых чисел ( p1 = =3, p2 = 7, p3 = 31, ). Все элементы G суть нечетные числа. Поскольку множества F и G содержат поровну элементов, 2 F и 2 G , делаем вывод, что в G найдется число, не входящее в F. Пришли к противоречию.

e

r 1

r2

j

e

k - 1, k

b

r1

b a,b g

e

-1
rn

rn-1

- 1, k - 1 =

j

j

=

b g c b g h e c b ghj



e

j

bg

+ 1 и an = 2 + 2 + Числа 2 2 + 1 взаимно просты, так как если бы у них был общий (нечетный) множиn -1 тель q, то их разность 2 2 +1 делилась бы на q, что неверно. Значит, при переходе от an к an+1 число простых делителей увеличивается. Поэтому у n-го члена рассматриваемой последовательности не менее n различных простых делителей. 9. Следующее доказательство возникает в результате рассмотрения представления числа n! в виде произведения степеней простых чисел:
n! =

2

n -1

делится на an .
2
n -1

I K I K

=
an.


p n

p.

fp

m

r

Как известно, кратность f p простого числа р в каноническом разложении числа n! определяется так: f p = k n p . Отсюда получаем оценку =


k 1

для кратности f : p

ch

fp


k

n p
k

=

n p -1
1 p -1

,

из которой следует, что
n

am - 1 M am

-1

- 1 M am

откуда am 1 mod ak , т.е. am и ak взаимно простые числа. 2 Для дальнейшего нам понадобится следующий результат. Лемма 2. Пусть k > 1, а, b натуральные числа. Тогда
(k 1, k 1) = k
a b (a, b)

c

-2

- 1 MKM ak

h

+1

- 1M ak ,

m

r

n!


p| n

p

(2)

(произведение берется по всем простым делителям n). Теперь докажем неравенство
n

n! n e .

(3)

1 ,

где (x, y) обозначает наибольший общий делитель чисел х и у. Доказательство. Рассмотрим сначала случай, когда а кратно b. Тогда для некоторого q имеем а = bq и a, b = = b. Доказываемое равенство приобреa b b тает вид k - 1, k - 1 = k 1 и a равносильно тому, что k 1 кратно

Когда число имеет 'много' простых делителей Новые доказательства теоремы Евклида можно получить, строя последовательности an , для которых число простых делителей n-го члена последовательности неограниченно возрастает.

Оно равносильно следующему неравенству: 1 ln 2 + ln 3 + K + ln n ln n - 1 . n Последнее доказывается суммирова-

b

g

bg

ch

нием неравенств ln k k = 1, 2, , n:

e

j

k -1

z
k

ln xdx , где

8. Докажем, что число an = 2
2
n -1

2

n

+

1 n
=

bln
1 n

2 + ln 3 + K + ln n x ln x - x

g

1 n

2 О сравнениях, малой теореме Ферма и функции Эйлера, которые встретятся читателю в этой статье, подробно рассказано в статье В.Сендерова и А.Спивака 'Малая теорема Ферма' ('Квант' ?1, 3, 4 за 2000 г.).

+2 + 1 имеет не менее n различных простых множителей. 4 2 В тождестве x + x + 1 = 2 2 = x + 1 - x x + 1 + x положим x =

b

g

n 1

=

1 n

b

z
n 1

ln xdx =

n ln n - n + 1 = 1 n > ln n - 1 .

g

e

je

j

= ln n - 1 +


МАТЕМАТИЧЕСКИЙ

КРУЖОК
m-2 2

37
+ + x + х + 1, где x N , то +x p 1 (mod m). Доказательство. Пусть р = mk + r, где r = 1, 2, , m 1. Нужно доказать, что r = 1. Из условия сразу следует:
x
m

Сопоставив неравенства (2) и (3), получим 1 n p p -1 . (4) e


p| n

следующем разделе мы рассмотрим некоторые простейшие частные случаи этой теоремы. Частные случаи теоремы Дирихле 11. Существует бесконечно много простых чисел вида 3n + 2. Пусть это не так и p1 = 2, p2 = 5, p3 = 11, , ps все простые числа указанного вида. Рассмотрим число k = 3 p1 p2 K ps 1. Очевидно, k не делится на 3, а также на p1 , p2 , , p s . Если бы все его простые делители при делении на 3 давали остаток 1, то тем же свойством обладало бы и число k, что неверно. Значит, у числа k есть простой делитель q вида q = 3n + 2. Число q отлично от p1 , , p s . Проти воречие. Ясно, что если 3n + 2 простое число, то n нечетно. Поэтому доказанное утверждение равносильно тому, что существует бесконечно много простых чисел вида 6n + 5. Более сложно доказывается такой факт. 12. Существует бесконечно много простых чисел вида 6n + 1. Предварительно убедимся в справедливости следующего утверждения. Лемма 3. Всякий простой делитель 2 р > 3 многочлена x + х + 1 имеет вид р = 6n + 1. Действительно, если р = 3k + 2 и 2 3 x + х + 1M p , то x 1 mod p и х не делится на р. Возведя обе части сравнения в степень k, полу-2 -1 чим x p 1 mod p . Отсюда x p x mod p . С другой стороны, по маp -1 лой теореме Ферма x 1 mod p . x 1 m od p , x 2 + Таким образом, +х + 1 3 mod p и р делится на 3. Полученное противоречие говорит о том, что простое число р при делении на 3 дает остаток 1, а значит, имеет вид р = 6n + 1. Теперь предположим, что p1 = 7, p2 = 13, , p s все простые числа вида 6n + 1. Пусть m = p1 ... p s и k = 2 = m + m + 1. Тогда число m имеет вид 2 m = 6r + 1 и k = 36 r + 18r + 3 3 mod 9 . Число k нечетно, не является степенью 3, поэтому у него есть простой делитель q > 3. По лемме 3 для некоторого n имеем q = 6n + 1. В то же время число q отлично от чисел p1 , , p s , так как при делении k на любое число pi в остатке будет 1. Противоречие получено. Рассуждения предыдущего пункта допускают обобщение. Лемма 4. Пусть m и р не равные друг другу простые числа. Если m -1 р является делителем числа x +

Если бы множество простых чисел было конечно, то левая часть неравенства (4) не могла бы быть сколько угодно большой вопреки (4). Полученное противоречие доказывает теорему Евклида. 10. Пусть P x многочлен с целыми коэффициентами. Назовем число k делителем многочлена P x , если для некоторого натурального n число P n делится на k. Докажем, что среди делителей многочлена P x степени 1 бесконечно много простых чисел. Предположим, что это не так, и список простых делителей P x исчерпывается числами p1 , p2 , , ps . Пусть P a = b 0 . Рассмотрим многочлен Q x = P a + bp1 p2 K p s x b . Поскольку P a + bp1 p2 K p s x P a M bp1 p2 K ps , имеем

1 m od p ,

b

g

(5)

bg

т.е. число х не делится на р. Убедимся сначала, что

bg

x

r -1

1 mod p .

bg

b

g

(6)

bg

bg bg

bg

Если p < m, то p = r и (6) выполняется в силу малой теоремы Ферма. Если p > m, то, возведя обе части сравнения p-r (5) в степень k = , получим m
x
p- r

1 m od p .

b

g

(7)

Q

M bp1 p2 K p s, b и значит, числа p1, K, p s не являются делителями Q x . Многочлен Q x , как всякий многочлен, отличный от константы, принимает каждое свое значение конечное число раз. Поэтому среди его значений есть числа, не равные 0,1 и 1, в силу чего у него есть простые делители. Между тем всякий делитель многочлена Q является и делителем многочлена Р, так как при t = a + bp1 p2 K p s x выполняется равенство P t = bQ x . Итак, многочлен P x имеет простой делитель, отличный от p1 , , p s . Противоречие. В частности, для всякой арифметической прогрессии an = a1 + n - 1 d , где d 0 , a Z , совокупность простых делителей ее членов бесконечна. Знаменитая теорема Дирихле утверждает, что если a1 и d взаимно простые числа, то среди членов арифметической прогрессии с первым членом a1 и разностью d содержится бесконечно много простых чисел.3 В
=

bg bxg - 1 = P c a + bp

c

c

h

h

С другой стороны, по малой теореме Ферма

x
p- r

p -1

1 mod p .

b

g

(8)

Вычитая из (8) сравнение (7), получа- 1 0 mod p . Отем, что x x сюда (поскольку х не делится на р) и следует (6). Доказывая лемму от противного, предположим, что r > 1. Тогда m и r 1 взаимно простые числа (так как m простое число и m r 1). Применим лемму 2:

1

p2 K p s x - P a

h bg

e

r -1

jb

g

bg

bg

b

g

b

g

b

g

e

x

m

- 1, x

r -1

-1 = x

j

b

m,r -1

g

- 1 = x - 1.

bg

bg

bg

b

g

b

b g

g

b

g

b

g

Из (5) и (6) следует, что число р m является общим делителем чисел x r -1 1 и x 1, значит, и их наибольшего общего делителя х 1. Таким образом, x 1 mod p . Отсюда P x m mod p , и, так как по условию леммы P x 0 mod p , приходим к выводу: m делится на р, что противоречит условию. Значит, r = 1. 13. Существует бесконечно много простых чисел вида mn + 1, где m простое число. Доказательство. Введем в рассмотрение многочлен

b

b g bg

g

bg

b

g

Px =x

bg

m -1

+x

m -2

2 + K + x + x + 1.

3 Интересно отметить, что ни для одного многочлена P x степени больше 1 не доказано, что среди чисел P n , n N , бесконечно много простых ([2], [4]). В то же время многочлен от двух переменных 2 2 ax + bxy + cy , где а, b и с взаимно простые числа, среди своих значений (при натуральных значениях аргументов) содержит бесконечно много простых чисел ([6]).

bg

bg

Пусть p1 , p2 , , p s все простые числа вида mn + 1. Определим число k равенством k = P p1 p2 K ps . По лемме 4 всякий простой делитель q числа k имеет вид q = mn + 1. В то же время число q отлично от чисел p1 , , p s , так как при делении k на любое число pi в остатке будет 1. Противоречие получено.

c

h


38
Комбинаторные доказательства 14. Пусть 2 > 1 + n . Докажем, что среди чисел 1, 2, 3, , 2 n существует по крайней мере m + 1 простое число. Предположим, среди чисел 1, 2, 3,... n ..., 2 содержится s m простых чисел p1 , p2 , , ps . Тогда каждое число, n не превосходящее 2 , представимо в k1 k2 ks виде p1 p2 K ps , где, очевидно, каждый показатель степени ki не больше n. Однако (по правилу произведения) r чисел такого вида 1 + n , что меньше n 2 . Полученное противоречие доказывает утверждение. Поскольку, как известно из анализа, показательная функция 'растет быстрее' степенной, и для любого (сколь угодно большого) m при достаn точно больших n неравенство 2 > m > 1 + n имеет место, получено доказательство бесконечности множества простых чисел. 15. Докажем сначала, что среди чисел 1, 2, K, n не менее четверти свободны от квадратов (т.е. не делятся на квадраты целых чисел). 4 Среди чисел 1, 2, K, n имеем не более n p2 чисел, делящихся на p2 . Поэтому количество чисел, делящихся на квадрат простого числа, не больше n n n <+ = 2 4 k k +1 p
n

КВАНT 2001/?1

b

g

m

грессией со знаменателем

b

g

b

g

l

q

l

q

< 1. Если p простых чисел конечное множество p1 , p2 ,K, ps , то, перемножив соответствующие им (положительные) сходящиеся ряды (9), вновь получим сходящийся ряд. В то же время его общий 1 член имеет вид k1 k2 k , где ki p1 p2 K ps s неотрицательные целые числа. В силу основной теоремы арифметики и сделанного предположения рассматриваемый ряд состоит из всех чисел вида 1 , т.е. является гармоническим ряn дом, который, как известно, не является сходящимся. Противоречие. Итак, расходимость гармонического ряда доказывает бесконечность множества простых чисел! Не менее удивительным является факт, легший в основу следующего доказательства. 17. Для каждого простого числа р имеем 2 1 1 1 p 1 + 2 + 4 + 6 +K= 2 . (10) p p p p -1

1

m

r

функция Эйлера мультипликативна, т.е. если числа n и m взаимно просты, то nm = n m . Докажем теперь теорему Евклида с помощью функции Эйлера. 18. Предполагая, что множество простых чисел конечно и состоит из чисел p1 , p2 , , ps , рассмотрим их произведение Р = p1 p2 K ps . Ни одно число, кроме 1, не может быть взаимно просто с Р, откуда P = 1.

b g bgb g

С другой стороны, P = p1 p2 K ps = = p1 - 1 p2 - 1 K ps - 1 > 1. Противоречие.
#

c

hc

hc

bg c h

bg

h

Топологическое доказательство

p n



=

n 4

b + n
k =2 k =2

FG H

g

1 k

-

1 k +1

IJ K

=

3n 4

.

Пусть теперь pk есть k-е простое число, k N . Первые (по возрастанию) k -1 k 1 простых чисел порождают 2 чисел, свободных от квадратов. Поk -1 = этому среди чисел от 1 до 4 2 k +1 =2 содержится по меньшей мере k простых чисел (в противном случае доля чисел, свободных от квадратов, k +1 была бы менее четверти), т.е. pk 2 . Это не только доказывает теорему Евклида, но и дает оценку сверху (разумеется, довольно грубую) для k-го простого числа. Гармонический ряд и трансцендентность числа 16 (Эйлер). Для каждого простого числа р ряд 1 1 1 1 + + 2 + 3 +K (9) pp p сходится, будучи геометрической про4 Отметим, что известен (см., например, [2]) следующий факт: доля чисел, свободных от квадратов, в множестве 6 12,... n с ростом n стремится к 2 = , = 0,6079

Если простых чисел конечное множество p1 , p2 , K , ps , то, перемножив соответствующие им (положительные) сходящиеся ряды (10), вновь получим сходящийся ряд с суммой S = 2 2 2 p p p = 2 1 2 2 K 2 s . Ясно, что p1 - 1 p2 - 1 ps - 1 S рациональное число. Общий член 1 ряда имеет вид 2 k1 2 k2 2 k , где ki p1 p2 K ps s неотрицательные целые числа. В силу основной теоремы арифметики и сделанного предположения рассматриваемый ряд состоит из всех чисел 1 вида 2 . Сумма такого ряда, как извеn 2 стно, равна . Для получения проти6 воречия осталось убедиться в том, что 2 иррационально. Действичисло 6 тельно, в противном случае число , будучи корнем уравнения с рацио2 2 x = нальными коэффициентами 6 6 = 0, было бы числом алгебраическим, в то время как это не так (доказательство трансцендентности числа мож но найти в [4]).

m

r

19 (Фюрстенберг, 1955). Введем на множестве целых чисел следующую топологию. Объявим открытыми множества, представимые в виде объединения бесконечных арифметических прогрессий. Проверка выполнения аксиом топологического пространства не сложна и предоставляется читателю. Рассмотрим множество Ap = = tp t Z . Оно не только открыто (будучи арифметической прогрессией с разностью р), но и замкнуто, так как дополнение к нему является объединением открытых множеств Ap,i = = tp + i t Z , i = 1, 2, , р 1. Если простых чисел конечное множество, то объединение конечного числа замк-

n n

s

s

нутых множество В =

U
p

Ap есть замк-

нутое множество. Любое число, отличное от 1 и 1, кратно некоторому простому числу и, значит, принадлежит множеству В. Стало быть, В = =Z\{1, 1}. Поэтому {1, 1} есть открытое множество (будучи дополнением к замкнутому множеству В), что противоречит определению открытого множества. Литература
[1] Литцман В. Теорема Пифагора. М.: ГИФМЛ, 1960. [2] Бухштаб А.А. Теория чисел. М.: Просвещение, 1966. [3] Виноградов И.М. Основы теории чисел. М.: Наука, 1981. [4] Галочкин А.И., Нестеренко Ю.В., Шидловский А.Б. Введение в теорию чисел. М.: Изд-во МГУ, 1995. [5] Полиа Г., Сеге Г. Задачи и теоремы из анализа. Т.2. М.: Наука, 1978. [6] Трост Э. Простые числа. М.: ГИФМЛ, 1959. [7] http://www.utm.edu.research/ primes. 5 Для 'знатоков'!

Функция Эйлера Функция Эйлера n число натуральных чисел, не превосходящих n и взаимно простых с n. Из определения следует, что если р простое число, то p = р 1. Известно ([4]), что

bg

l

q

bg