Главная Перейти к главной странице
Введение I. Теория чисел Теорема Вильсона Две теоремы Ферма Распределение простых чисел Неравенства Чебышева II. Анализ III. Модели IV. Задачи
Обозначения Литература

ДВЕ ТЕОРЕМЫ ФЕРМА

Выдающийся французский учёный XVII в. Пьер Ферма (Pierre de Fermat), занимавшийся математикой исключительно ради собственного удовольствия, в теории чисел получил множество исключительно красивых результатов.


P.Fermat
Рис. 1. П. Ферма (1601–1665)

Не касаясь знаменитой Большой теоремы, приведём здесь доказательства лишь двух его утверждений, выделяющихся своим изяществом даже на фоне других замечательных работ Ферма.

МАЛАЯ ТЕОРЕМА ФЕРМА

Теорема 2.1 (Ферма) Если натуральное число a не делится на простое число p, то выполняется сравнение ap − 1 ≡ 1   (mod p).

Обратное утверждение не верно: например, a = 2, p = 341 = 11 ∙ 31.

Доказательство. Используем формулу бинома Ньютона. Для любых вещественных x, y и натурального n выполняется тождество

(x + y)n = n k = 0 Ckn xn − kyk.

В частности, при x = y = 1 получим

n k = 0 Ckn = 2n,
где биномиальные коэффициенты
Ckn = n! k!(n − k)!
содержательно выражают количество сочетаний из n элементов по k, то есть количество k-элементных подмножеств n-элементного множества. Из определения количества сочетаний следует полезная формула Ck + 1n + 1 = Ckn + Ck + 1n.

Переходя непосредственно к доказательству, во-первых, замечаем из (5), что все биномиальные коэффициенты — целые числа, во-вторых, из определения их (4) вытекает делимость Ckn (0 < k < p) на p: так как p — простое, то оно не может сократиться ни на одно из чисел, стоящих в знаменателе. Следовательно, для простого p имеем сравнение (x1 + x2)p ≡ xp1 + xp2   (mod p),

которое легко обобщается (по индукции) на любое количество a слагаемых: (x1 + x2 + … + xa)p ≡ xp1 + xp2 + ... + xpa   (mod p). И, наконец, последний шаг доказательства — положить x1 = x2 = ... = xa = 1 .

Простое число как сумма двух квадратов

Легко видеть, что каждое из нечётных простых чисел 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

может при делении на 4 давать в остатке либо 1, либо 3. Следовательно, всё множество простых чисел (кроме 2) распадается на два подмножества: числа вида 4n + 1 и числа вида 4n + 3. Рассматривая таблицу простых чисел можно заметить, что простые числа первого типа разлагаются на сумму квадратов: 5 = 12 + 22, 13 = 22 + 32, 29 = 22 + 52, ... а числа вида 4n + 3 такого представления не имеют.

Нетрудно показать, что вообще для любых чисел вида 4n + 3 (не обязательно простых) разложение в сумму квадратов невозможно. Действительно, квадрат четного числа всегда делится на 4, а квадрат нечётного при делении на 4 даёт в остатке 1: (2m + 1)2 = 4(m2 + m) + 1. Следовательно, сумма квадратов может при делении на 4 давать в остатке лишь 0, 1 или 2. Теорему Ферма о представлении простых чисел первого типа Г. Харди считал «одной из наиболее совершенных в математике» [1].

Теорема 2.2 (Ферма) Любое простое число вида 4n + 1 есть сумма двух квадратов натуральных чисел.

Красивая идея доказательства, приводимого ниже, принадлежит норвежскому математику А. Туэ (Axel Thue) [5]. Нам потребуется следующая

Лемма 2.1. Если простое p имеет вид 4n + 1, то найдётся целое q, такое что q2 + 1 ≡ 0   (mod p).

Доказательство. По теореме Вильсона, так как p = 4n + 1, имеем (p − 1)! + 1 = (4n)! + 1 ≡ 0   (mod p)

или (p − 1)! + 1 = (2n)!((p − 2n)(p − 2n + 1) … (p − 1)) + 1 = = (2n)! (Ap + (−1)2n2n(2n − 1) … 1) + 1 = = Bp + ((2n)!)2 + 1 ≡ 0   (mod p), где A, B — некоторые целые числа. Отсюда следует, что ((2n)!)2 + 1 ≡ 0   (mod p), то есть найдено число, удовлетворяющее условиям леммы, а именно q = (2n)! = ((p − 1)/2)!    

Доказательство теоремы 2.2. Рассмотрим множество M всех пар натуральных чисел (a, b), таких что 0 ≤ a ≤ p,   0 ≤ b ≤ p.

Общее количество всех таких пар равно ([p] + 1)2, что больше, чем p. Следовательно, для любого натурального числа q величины разностей a − qb   (mod p), образуемых, когда a и b независимо друг от друга пробегают все свои возможные значения 0, 1, … , [p], не все между собой различны*. Другими словами, найдутся различные пары (a1, b1), (a2, b2), для которых a1 − qb1 ≡ a2 − qb2   (mod p) и, следовательно, a1 − a2 ≡ q(b1 − b2)   (mod p)

Положив x = |a1 − a2|, y = |b1 − b2| получим пару (x, y) из множества M, для которой выполняется сравнение x ≡ ±qy   (mod p). Очевидно, одновременно x, y не могут обращаться в 0, так как пары (a1, b1) и (a2, b2) были различными.

Возвышая, последнее сравнение в квадрат, получим x2 ≡ q2y2   (mod p),

где выберем q так, чтобы q2 ≡ −1   (mod p) (это возможно в силу леммы 2.1). Тогда x2 ≡ −y2   (mod p), и, поскольку для x, y, как и для всех пар чисел из M, выполняется соотношение 0 < x2 + y2 < 2p, заключаем (так как единственное число в интервале ]0; 2p[, делящееся на p — это само число p) что x2 + y2 = p.    



* Возьмём, к примеру, p = 13, тогда [p ] = 3 и a, b независимо друг от друга пробегают числа 0, 1, 2, 3. Выберем q = 5, тогда a − 5b (mod 13) будет иметь следующие значения:

a\b 0 1 2 3
0 0 8 3 11
1 1 9 4 12
2 2 10 5 0
3 3 11 6 1

Совпадающие значения выделены.