Онлайн калькуляторы

На нашем сайте собрано более 100 бесплатных онлайн калькуляторов по математике, геометрии и физике.

Справочник

Основные формулы, таблицы и теоремы для учащихся. Все что нужно, чтобы сделать домашнее задание!

Заказать решение

Не можете решить контрольную?!
Мы поможем! Более 20 000 авторов выполнят вашу работу от 100 руб!

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

ТЕОРЕМА
Великая теорема Ферма. Для любого натурального числа 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.

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