накові залишки при діленні на p помилково. Запішемето:
a? r1 (mod p);
a? r2 (mod p);
...
(p - 1) a? rp - 1 (modp);
Використовуючи властивості порівняння перемножуємо попередні порівняння. Так як усього множників p - 1, а всі залишки при діленні на p різні, то праворуч буде (p - 1)! br/>
ap - 1 (p - 1)! ? (P - 1)! (Modp);
(ap - 1 - 1) (p - 1)! ? 0 (modp);
Але (p - 1)! не ділиться на p, так як p - просте, а всі множники факторіала менше p. Значить (ap - 1 - 1) ділиться на p. br/>
(ap - 1 - 1)? 0 (mod p); - 1? 1 (mod p);? a (modp);
Що і потрібно було довести.
Приклад 1.
Обчислити залишок від ділення ступеня 34746 на 13.
Рішення:
За малої теореми Ферма, якщо p - просте, то залишок від ділення ступеня ар-1 на р дорівнює 1. p align="justify"> Тому при обчисленні залишку від ділення 34746 на 13 ми можемо не тільки відразу зменшити підставу ступеня до 8 - залишку від ділення 34 на 13, але помітивши, що 812 при діленні на 13 дає залишок 1, записуємо далі :
= 812 * 62 +1 = 812 * 62 * 8, тому шуканий залишок дорівнює 8.
Приклад 2.
Який залишок при діленні на 17 дає число 96514?
Рішення:
Мала теорема Ферма допомагає замінити задану ступінь ступенем з маленьким показником: замість показника ступеня розглядається його залишок від ділення на 16.
Завдання істотно спростилася, а подальше рішення зручно провести за допомогою порівнянь, розглядаючи порівняння за модулем 17. Оскільки 96 = 11 = -6, то
? (-6)? -63? -36 * 6? -12? 5
Фермісти
У той час у колі математиків з'явилося напівпрезирливе прізвисько - ферміст. Так називали всякого самовпевненого вискочку, якому не вистачало знань, але зате з лишком вистачало амбіцій для того, щоб поспіхом спробувати силоньки у доказі Великої теореми, а потім, не помітивши власних помилок, гордо ляснувши себе в груди, голосно заявити: В«Я перший довів теорему Ферма! В». Кожен ферміст, будь він хоч навіть десятитисячним по рахунку, вважав себе першим - це і було смішним. Простий зовнішній вигляд Великої теореми так сильно нагадував фермістам легку здобич, що їх абсолютно не бентежило, що навіть Ейлер з Гаусом не змогли впоратися з нею. p align="justify"> Але повністю довести теорему Ферма не може ніхто.
Для випадку n = 3 цю теорему в Х столітті намагався довести ал-Ходжанді, але його доказ не збереглося.
Ейлер в 1770 році довів теорему для випадку n = 3, Діріх...
