две теоремы ферма

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

Теорема 2.1 (Ферма) Если натуральное число $a$ не делится на простое число $p$, то выполняется сравнение \begin{equation} \label{FERMATformula} a^{p - 1} \equiv 1 \quad (\mathrm{mod}~p). \end{equation} Обратное утверждение не верно: например, $a = 2$, $p = 341 = 11 \cdot 31$.

Доказательство. Используем формулу бинома Ньютона: для любых вещественных $x$, $y$ и натурального $n$ выполняется тождество \begin{equation} \label{BINOMformula} (x + y)^n = \sum_{k=0}^n C_n^k x^k y^{n-k}. \end{equation} В частности, при $x = y = 1$ получим \begin{equation} \label{2Nformula} 2^n = \sum_{k=0}^n C_n^k, \end{equation} где биномиальные коэффициенты \begin{equation} \label{KoeffBinomformula} C_n^k = \frac{n!}{k!(n - k)!} \end{equation} содержательно выражают количество сочетаний из $n$ элементов по $k$, то есть количество $k$-элементных подмножеств $n$-элементного множества. Из определения количества сочетаний следует полезная формула \begin{equation} \label{BINOM_KOEFSformula} C_{n+1}^{k+1} = C_n^k + C_n^{k+1}. \end{equation}

Переходя непосредственно к доказательству, во-первых, замечаем из (\ref{BINOM_KOEFSformula}), что все биномиальные коэффициенты — целые числа, во-вторых, из определения их (\ref{KoeffBinomformula}) вытекает делимость $C_n^k$ $(0 < k < p)$ на $p$: так как $p$ — простое, то оно не может сократиться ни на одно из чисел, стоящих в знаменателе. Следовательно, для простого $p$ имеем сравнение $$ (x_1 + x_2)^p \equiv x_1^p + x_2^p \quad (\mathrm{mod}~p), $$ которое легко обобщается (по индукции) на любое количество $a$ слагаемых: $$ (x_1 + \ldots + x_a)^p \equiv x_1^p + \ldots + x_a^p. $$ И осталось, наконец, сделать последний шаг доказательства, который состоит в том, чтобы положить $x_1 = x_2 = \ldots = x_a = 1$. ♦

Легко видеть, что каждое из нечётных простых чисел $$ 3, 5, 7, 11, 13, 17, 19, 23, 29, \ldots $$ может при делении на $4$ давать в остатке либо $1$, либо $3$. Следовательно, всё множество простых чисел (кроме $2$) распадается на два подмножества: числа вида $4n + 1$ и числа вида $4n + 3$. Рассматривая таблицу простых чисел можно заметить, что простые числа первого типа разлагаются на сумму квадратов: $$ 5 = 1^2 + 2^2, 13 = 2^2 + 3^2, \ldots $$ а числа вида $4n + 3$ такого представления не имеют.

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

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

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

Лемма 2.1. Если простое $p$ имеет вид $4n + 1$, то найдётся целое $q$, такое что $$ q^2 + 1 \equiv 0 \quad (\mathrm{mod}~p). $$

Доказательство. По теореме Вильсона, так как $p = 4n + 1$, имеем $$ (p - 1)! + 1 = (4n)! + 1 \equiv 0 \quad (\mathrm{mod}~p) $$ или \begin{eqnarray*} && (p - 1)! + 1 = \\ &&= (2n)!\big((p - 2n)(p - 2n + 1) \ldots \\ &&\ldots (p - 1)\big) + 1 = (2n)! \big(Ap + \\ &&+ (-1)^{2n} 2n(2n - 1) \ldots 1\big) + 1 = \\ &&= Bp + \big((2n)!\big)^2 + 1 \equiv \\ &&\equiv 0 \quad (\mathrm{mod}~p), \end{eqnarray*} где $A$, $B$ — некоторые целые числа, величину которых, при желании, легко определить. Отсюда следует, что $$ \big((2n)!\big)^2 + 1 \equiv 0 \quad (\mathrm{mod}~p), $$ то есть найдено число, удовлетворяющее условиям леммы, а именно $$ q = (2n)! = \big((p - 1)/2 \big)!, $$ что и завершает наше вполне конструктивное доказательство. ♦

Доказательство теоремы 2.2. Рассмотрим множество $M$ всех пар натуральных чисел $(a, b)$, таких что $0 \le a \le \sqrt{p}$, $0 \le b \le \sqrt{p}$ Общее количество всех таких пар равно $\big([\sqrt{p}] + 1\big)^2$, что больше, чем $p$. Следовательно, для любого натурального числа $q$ величины разностей $a - qb$ $(\mathrm{mod}~p)$, образуемых, когда $a$ и $b$ независимо друг от друга пробегают все свои возможные значения $0, 1, \ldots, [\sqrt{p}]$, не все между собой различны**. Другими словами, найдутся различные пары $(a_1, b_1)$, $(a_2, b_2)$, для которых $$ a_1 - qb_1 \equiv a_2 - qb_2 \quad (\mathrm{mod}~p) $$ и, следовательно, $$ a_1 - a_2 \equiv q(b_1 - b_2) \quad (\mathrm{mod}~p) $$

Положив $x = |a_1 - a_2|$, $y = |b_1- b_2|$ получим пару $(x, y)$ из множества $M$, для которой выполняется сравнение $$ x \equiv \pm qy \quad (\mathrm{mod}~p). $$ Очевидно, одновременно $x$, $y$ не могут обращаться в $0$, так как пары $(a_1, b_1)$ и $(a_2, b_2)$ были различными. Возвышая, последнее сравнение в квадрат, получим $$ x^2 \equiv q^2 y^2 \quad (\mathrm{mod}~p), $$ где выберем $q$ так, чтобы $q^2 \equiv - 1 \quad (\mathrm{mod}~p)$ (это возможно в силу леммы 2.1). Тогда $$ x^2 \equiv - y^2   \quad (\mathrm{mod}~p), $$ и, поскольку для $x$, $y$, как и для всех пар чисел из $M$, выполняется соотношение $$ 0 < x^2 + y^2 < 2p, $$ заключаем (так как единственное число в интервале $]0; 2p[$, делящееся на $p$ — это само число $p$), что $$ x^2 + y^2 = p, $$ что и требовалось доказать. ♦