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

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

КРУЖОК
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