Теорема Ферма

ТЕОРЕМА

Великая теорема Ферма. Для любого натурального числа $n$ большего 2 уравнение $x^{n} + y^{n} = z^{n}$ не имеет ненулевых решений в целых числах.

Над её доказательством около 350 лет работало много ученых. И в 1994 году она была полностью доказана Эндрю Уайлсом.

ТЕОРЕМА

Малая теорема Ферма. Если $p$ – простое число и $a$ – целое число, не делящееся на $p$ , то $a^{p-1}-1$ делится на $p$ , то есть $a^{p-1}-1 \equiv 1 (\text{mod } p)$ .

Два целых числа $a$ и $b$ называются сравнимы по модулю натурального числа $n$ , если при делении на $n$ они дают одинаковые остатки; или если их разность делится на $n$ . Записывается это следующим образом

$a \equiv b (\text{mod } n)$

Примеры решения задач

ПРИМЕР 1

Задание

Записать и проверить малую теорему Ферма для $p=3$ и $a=4$ .

Решение

По малой теореме Ферма $a^{p-1}-1$ делится на $p$ . Подставляя заданные значения $a$ и $p$ , получим:

$4^{3-1} -1 \vdots 3$

Действительно, $4^{2} -1 = 16-1=15\vdots 3$

Для заданных значений теорема верна.

ПРИМЕР 2

Задание

Найти остаток от деления $3^{102}$ на 101.

Решение

Число 101 является простым числом. Согласно малой теореме Ферма имеет место следующее сравнение:

$3^{100} \equiv 1 (\text{mod } 101)$

Домножим правую и левую часть этого сравнения на 9, получим:

$9 \cdot 3^{100} \equiv 9 \cdot 1 (\text{mod } 101)$

$3^{2} \cdot 3^{100} \equiv 9 (\text{mod } 101)$

$3^{102} \equiv 9 (\text{mod } 101)$

Ответ

Остаток от деления $3^{102}$ на 101 равен 9

ПРИМЕР 3

Задание

Доказать, что $7^{120}-1$ делится на 143.

Решение

Разложим 143 на простые множители:

$143 = 11 \cdot 13$

Покажем, что $7^{120}-1$ делится на 11 и на 13. Действительно, по теореме Ферма $7^{10} \equiv 1 (\text{mod } 11)$ и $7^{12} \equiv 1 (\text{mod } 13)$ . По свойству сравнений, если $a \equiv b (\text{mod } m)$ , то для любого натурального $n$ , справедливо $a^{n} \equiv b^{n} (\text{mod } m)$ . Тогда последние два сравнения можно переписать в виде $\left( 7^{10} \right)^{12} \equiv 1 (\text{mod } 11)$ и $\left( 7^{12} \right)^{10} \equiv 1 (\text{mod } 13)$ . Таким образом, $7^{120}-1$ делится на 11 и на 13, а, следовательно, делится и на 143.

Что и требовалось доказать.

Понравился сайт? Расскажи друзьям!