Маленька теорема Ферма

У цій публікації ми розглянемо одну з основних теорем теорії цілих чисел –  Маленька теорема Ферманазваний на честь французького математика П'єра де Ферма. Також розберемо приклад розв’язання задачі для закріплення викладеного матеріалу.

Формулювання теореми

1. Початковий

If p є простим числом a є цілим числом, яке не ділиться на pпотім a^р-1 - 1 поділене на число p.

Формально це записується так: a^р-1 ≡ 1 (проти p).

Примітка: Просте число — це натуральне число, яке ділиться лише на XNUMX і само собою без залишку.

Наприклад:

• a = 2
• p = 5
• a^р-1 - 1 = 2^{5 - 1} - 1 = 2⁴ – 1 = 16 – 1 = 15
• номер 15 поділене на число 5 без залишку.

2. Альтернатива

If p є простим числом, a будь-яке ціле число, тоді a^p порівнянні з a модуль p.

a^p ≡ а (проти p)

Історія пошуку доказів

П'єр де Ферма сформулював теорему в 1640 році, але сам не довів її. Пізніше це зробив Готфрід Вільгельм Лейбніц, німецький філософ, логік, математик тощо. Вважається, що він уже мав доказ у 1683 році, хоча він ніколи не був опублікований. Примітно, що Лейбніц відкрив теорему сам, не знаючи, що вона вже була сформульована раніше.

Перший доказ теореми було опубліковано в 1736 році, і воно належить швейцарському, німецькому математику і механіку Леонгарду Ейлеру. Мала теорема Ферма є окремим випадком теореми Ейлера.

Приклад задачі

Знайти залишок від числа 2¹² on 12.

рішення

Давайте уявимо число 2¹² as 2⋅2¹¹.

11 є простим числом, тому за маленькою теоремою Ферма ми отримуємо:

2¹¹ ≡ 2 (проти 11).

Отже, 2⋅2¹¹ ≡ 4 (проти 11).

Отже, число 2¹² поділене на число 12 з залишком рівним 4.