Разделы 
Дополнительно
Задача по математике - 3052
2019-05-06 
Теорема Ферма. Доказать, что если $p$ есть простое число, то разность $a^p-a$ при любом целом $a$ делится на $p$.
Решение:
Первое решение. Пусть $a$ не делится на $p$. В таком случае числа $a, 2a, 3a, \cdots, (p-l)a$ тоже не будут делиться на $p$ и все будут давать при делении на $p$ разные остатки: действительно, если бы $ka$ и $la$ (где $p - 1 \geq k > l$) давали бы при делении на $p$ одинаковые остатки, то разность $ka - la - (k- l)a$ делилась бы на $p$, что невозможно, так как $p$ простое, а не делится на $p$ и $k - l$ меньше $p$. Но все возможные остатки при делении на $p$ исчерпываются $p - 1$ числами $1, 2, 3, \cdots, p - 1$. Таким образом, должно быть:
$a = q_1p + a_1, 2a = q_2p + a_2, 3a = q_3p + a_3, \cdots, (p - 1)a = q_{p-1}p + a_{p-1}$,
где $a_1, a_2, \cdots, a_{p-1}$ - числа $1, 2, \cdots, p-1$, взятые в каком-то порядке. Перемножая все эти равенства, получим:
$[1 \cdot 2 \cdot \cdots \cdot (p-1)] a^{p-1} = N_p + a_1a_2 \cdots a_{p-1}$,
или
$[1 \cdot 2 \cdot \cdots \cdot (p-1)] (a^{p-1} - 1) = Np$.
Отсюда следует, что $a^{p-1} - 1$ делится на $p$, а значит, и $a^p - a$ делится на $p$.
Если $a$ делится на $p$, то утверждение теоремы Ферма является очевидным.
Второе решение. Теорема является очевидной при $a = 1$, так как в этом случае $a^p - a = 1 - 1 =0$ делится на любое число. Будем теперь доказывать ее методом математической индукции, т. е. предположим, что нам уже известно, что $a^p - a$ делится на $p$, и докажем, что в этом случае $(a + 1)^p - (a + 1)$ делится на $p$.
По формуле бинома Ньютона
$(a + 1)^p -(a + 1) = a^p + pa^{p-1} + С_p^2 a^{p -2} + C_p^3 a^{p-3} + \cdots + pa + 1 - a - 1 = (a^p - a) + pa^{p-1} + C_p^2 a^{p -2} + \cdots + C_p^{p-2}a^2 + pa$.
Но все биномиальные коэффициенты
$C_p^k = \frac {p(p-1)(p-2) \cdots (p-k+1)}{1 \cdot 2 \cdot 3 \cdots k}$
делятся на простое число $p$, так как числитель выписанного выражения содержит множитель $p$, а знаменатель не содержит этого множителя. А так как, по предположению, и $a^p - a$ делится на $p$, то $(a + 1)^p - (a + 1)$ делится на $p$.
Теорема Ферма. Доказать, что если $p$ есть простое число, то разность $a^p-a$ при любом целом $a$ делится на $p$.
Решение:
Первое решение. Пусть $a$ не делится на $p$. В таком случае числа $a, 2a, 3a, \cdots, (p-l)a$ тоже не будут делиться на $p$ и все будут давать при делении на $p$ разные остатки: действительно, если бы $ka$ и $la$ (где $p - 1 \geq k > l$) давали бы при делении на $p$ одинаковые остатки, то разность $ka - la - (k- l)a$ делилась бы на $p$, что невозможно, так как $p$ простое, а не делится на $p$ и $k - l$ меньше $p$. Но все возможные остатки при делении на $p$ исчерпываются $p - 1$ числами $1, 2, 3, \cdots, p - 1$. Таким образом, должно быть:
$a = q_1p + a_1, 2a = q_2p + a_2, 3a = q_3p + a_3, \cdots, (p - 1)a = q_{p-1}p + a_{p-1}$,
где $a_1, a_2, \cdots, a_{p-1}$ - числа $1, 2, \cdots, p-1$, взятые в каком-то порядке. Перемножая все эти равенства, получим:
$[1 \cdot 2 \cdot \cdots \cdot (p-1)] a^{p-1} = N_p + a_1a_2 \cdots a_{p-1}$,
или
$[1 \cdot 2 \cdot \cdots \cdot (p-1)] (a^{p-1} - 1) = Np$.
Отсюда следует, что $a^{p-1} - 1$ делится на $p$, а значит, и $a^p - a$ делится на $p$.
Если $a$ делится на $p$, то утверждение теоремы Ферма является очевидным.
Второе решение. Теорема является очевидной при $a = 1$, так как в этом случае $a^p - a = 1 - 1 =0$ делится на любое число. Будем теперь доказывать ее методом математической индукции, т. е. предположим, что нам уже известно, что $a^p - a$ делится на $p$, и докажем, что в этом случае $(a + 1)^p - (a + 1)$ делится на $p$.
По формуле бинома Ньютона
$(a + 1)^p -(a + 1) = a^p + pa^{p-1} + С_p^2 a^{p -2} + C_p^3 a^{p-3} + \cdots + pa + 1 - a - 1 = (a^p - a) + pa^{p-1} + C_p^2 a^{p -2} + \cdots + C_p^{p-2}a^2 + pa$.
Но все биномиальные коэффициенты
$C_p^k = \frac {p(p-1)(p-2) \cdots (p-k+1)}{1 \cdot 2 \cdot 3 \cdots k}$
делятся на простое число $p$, так как числитель выписанного выражения содержит множитель $p$, а знаменатель не содержит этого множителя. А так как, по предположению, и $a^p - a$ делится на $p$, то $(a + 1)^p - (a + 1)$ делится на $p$.
