Мала теорема Ферма: відмінності між версіями

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[неперевірена версія][перевірена версія]
Вилучено вміст Додано вміст
DobosevycH (обговорення | внесок)
Немає опису редагування
 
(Не показані 38 проміжних версій 26 користувачів)
Рядок 1: Рядок 1:
'''Мала теорема Ферма''' — одне з основних тверджень елементарної [[теорія чисел|теорії чисел]]. Вперше була сформульована в листі французького математика [[П'єр Ферма|П'єра де Ферма]] до свого друга Френікля де Бессі [[18 жовтня]] [[1640]] року. В листі проте не було наведено доведення. Перше відоме доведення подане [[Ґотфрід Вільгельм Лейбніц|Лейбніцом]] у неопублікованих рукописах.
'''Мала теорема Ферма''' — одне з основних тверджень елементарної [[теорія чисел|теорії чисел]]. Вперше була сформульована в листі французького математика [[П'єр Ферма|П'єра де Ферма]] до свого друга {{нп|Френікль де Бессі|Френікля де Бессі||Bernard Frénicle de Bessy}} [[18 жовтня]] [[1640]] року. В листі проте не було наведено доведення. Перше відоме доведення подане [[Ґотфрід Вільгельм Лейбніц|Лейбніцом]] у неопублікованих рукописах.



== Формулювання ==
== Формулювання ==
Рядок 8: Рядок 7:
: <math>\ a^{p-1} \equiv 1 \pmod{p}</math>.
: <math>\ a^{p-1} \equiv 1 \pmod{p}</math>.


Еквівалентним є наступне твердження:
Еквівалентним є наступне твердження: Нехай <math>\ p</math>&nbsp;— [[просте число|просте]], <math>\ a</math>&nbsp;— довільне [[ціле число]]. Тоді:

Нехай <math>\ p</math>&nbsp;— [[просте число|просте]], <math>\ a</math>&nbsp;— довільне [[ціле число|ціле]] число. Тоді:
: <math>\ a^p - a \equiv 0 \pmod p</math>.
: <math>\ a^p - a \equiv 0 \pmod p</math>.


Рядок 29: Рядок 26:
: <math>{p \choose k} = \frac{p(p-1)(p-2)\cdots (p-k+1)}{k!} </math>&nbsp;— [[біноміальний коефіцієнт]].
: <math>{p \choose k} = \frac{p(p-1)(p-2)\cdots (p-k+1)}{k!} </math>&nbsp;— [[біноміальний коефіцієнт]].
Тоді для простого <math>\ p</math> і <math>\ 0<k<p</math> маємо, що <math>{p \choose k}</math> ділиться на <math>\ p </math>.
Тоді для простого <math>\ p</math> і <math>\ 0<k<p</math> маємо, що <math>{p \choose k}</math> ділиться на <math>\ p </math>.
Справді можна записати <math>{p \choose k}= \frac{pm}{k!}\quad\quad </math> де <math>\quad\quad m=(p-1)(p-2)\cdots (p-k+1)</math>. Оскільки <math>\ p</math> і <math>\ k! </math> є взаємно-простими, то, очевидно, що <math>\ k!</math> ділить <math>\ m </math> і, як наслідок <math>{p \choose k}</math> ділиться на <math>\ p </math>.
Справді можна записати <math>{p \choose k}= \frac{pm}{k!}\quad\quad, </math> де <math>\quad\quad m=(p-1)(p-2)\cdots (p-k+1)</math>. Оскільки <math>\ p</math> і <math>\ k! </math> є взаємно-простими, то, очевидно, що <math>\ k!</math> ділить <math>\ m </math> і, як наслідок <math>{p \choose k}</math> ділиться на <math>\ p </math>.
Твердження Малої теореми Ферма доводитимемо [[Математична індукція|методом математичної індукції]]. Теорема очевидно справедлива для <math>\ a=1 </math>.
Твердження Малої теореми Ферма доводитимемо [[Математична індукція|методом математичної індукції]]. Теорема очевидно справедлива для <math>\ a=1 </math>.
Припустимо, що вона справджується для певного цілого <math>\ a</math>. Згідно формули [[біном Ньютона|бінома Ньютона]], використовуючи раніше доведене і припущення індукції одержуємо:
Припустимо, що вона справджується для певного цілого <math>\ a</math>. Згідно з формулою [[біном Ньютона|бінома Ньютона]], використовуючи раніше доведене і припущення індукції одержуємо:
: <math>(a+1)^p \equiv a^p + a^0 + \sum_{k=1}^{p-1}{p \choose k}a^k \equiv a^p + 1 \equiv a + 1\pmod{p}</math>.
: <math>(a+1)^p \equiv a^p + a^0 + \sum_{k=1}^{p-1}{p \choose k}a^k \equiv a^p + 1 \equiv a + 1\pmod{p}</math>.
тобто
тобто
<math>(a+1)^p - (a+1) \equiv 0 \pmod p</math>, що доводить твердження для додатніх цілих. Для від'ємних доведення аналогічне.
<math>(a+1)^p - (a+1) \equiv 0 \pmod p</math>, що доводить твердження для додатних цілих. Для від'ємних доведення аналогічне.


=== Доведення 2 (використовуючи лишки) ===
=== Доведення 2 (використовуючи лишки) ===


Припустимо, що <math>\ a</math> додатнє число, що не ділиться на <math>\ p</math>.
Припустимо, що <math>\ a</math> [[додатне число]], що не ділиться на <math>\ p</math>.
<!--
<!--
NOTE: Of course this proof also works for negative ''a''. However, I'm really just trying to strip it down to the simplest possible version, that people only marginally familiar with modular arithmetic will understand. I didn't want to get stuck with stuff like "replace ka by its representative in the set {1, 2, p-1}. (Dmharvey)
NOTE:
Of course this proof also works for negative ''a''. However, I'm really just trying to strip it down to the simplest possible version, that people only marginally familiar with modular arithmetic will understand. I didn't want to get stuck with stuff like "replace ka by its representative in the set {1, 2, ... p-1}. (Dmharvey)


What if a is divisible by p?
What if a is divisible by p?
-->
-->
Якщо записати
Якщо записати
Рядок 64: Рядок 60:
=== Доведення 3 ([[Комбінаторика|комбінаторне]]) ===
=== Доведення 3 ([[Комбінаторика|комбінаторне]]) ===


Припустимо, що ми маємо бусинки <math>\ a </math> різних кольорів і нам потрібно зробити з них намисто довжиною <math>\ p </math> бусинок. Для початку зробимо стрічку з <math>\ p </math> бусинок. Існує <math>\ a^p </math> різних стрічок. Відкинемо всі однотонні стрічки їх всього <math>\ a </math>. Залишеться <math>\ a^p-a </math> різних стрічок. З'єднаємо початок кожної стрічки з її кінцем. Тепер деякі намиста стали однаковими, якщо їх повернути. Оскільки існує <math>\ p </math> різних циклічних перестановок то існує <math>\ \frac{a^p-a}{p} </math> різних намист. Виходячи з інтерпритація числа <math>\ \frac{a^p-a}{p} </math> воно ціле.
Припустимо, що ми маємо намистинки <math>\ a </math> різних кольорів і нам потрібно зробити з них намисто довжиною <math>\ p </math> намистинок. Для початку зробимо стрічку з <math>\ p </math> намистинок. Існує <math>\ a^p </math> різних стрічок. Відкинемо всі однотонні стрічки їх всього <math>\ a </math>. Залишається <math>\ a^p-a </math> різних стрічок. З'єднаємо початок кожної стрічки з її кінцем. Тепер деякі намиста стали однаковими, якщо їх повернути. Оскільки існує <math>\ p </math> різних циклічних перестановок то існує <math>\ \frac{a^p-a}{p} </math> різних намист. Виходячи з інтерпретації числа <math>\ \frac{a^p-a}{p} </math> воно ціле.


== Дивись також ==
== Див. також ==
* [[Число Кармайкла|Числа Кармайкла]]&nbsp;— псевдопрості числа
* [[Теорема Ферма]]
* [[Теорема Ферма]]
* [[Теорема Ферма (велика)]]
* [[Теорема Ферма (велика)]]


== Джерела ==
== Джерела ==
* {{cite book|
* Ойстин Оре (2003). Приглашение в теорию чисел. М.:Едиториал УРСС. ISBN 5-354-00252-4.
title= Приглашение в теорию чисел|
* Arthur Engel (1997). ''Problem-Solving Strategies''. New York: Springer-Verlag. ISBN 0-387-98219-1.
author= Ойстин Оре |
year= 2003|
publisher=Едиториал УРСС.| location=Москва|
isbn= 5-354-00252-4
}}


* {{cite book|
[[Категорія:Теореми]]
title= Problem-Solving Strategies|
author= Arthur Engel|
year= 1997|
publisher=Springer-Verlag| location=New York|
isbn= 0-387-98219-1
}}

[[Категорія:Теореми в теорії чисел]]
[[Категорія:Модульна арифметика]]
[[Категорія:Модульна арифметика]]
[[Категорія:Тести простоти]]
[[Категорія:Тести простоти]]
[[Категорія:1640 у науці]]
{{Link GA|es}}

[[ar:مبرهنة فيرما]]
[[bg:Малка теорема на Ферма]]
[[ca:Petit teorema de Fermat]]
[[cs:Malá Fermatova věta]]
[[de:Kleiner fermatscher Satz]]
[[en:Fermat's little theorem]]
[[eo:Malgranda teoremo de Fermat]]
[[es:Pequeño teorema de Fermat]]
[[fa:قضیه کوچک فرما]]
[[fi:Fermat'n pieni lause]]
[[fr:Petit théorème de Fermat]]
[[he:המשפט הקטן של פרמה]]
[[hu:Kis Fermat-tétel]]
[[id:Teorema kecil Fermat]]
[[it:Piccolo teorema di Fermat]]
[[ja:フェルマーの小定理]]
[[ka:ფერმას მცირე თეორემა]]
[[kk:Ферманың кіші теоремасы]]
[[ko:페르마의 소정리]]
[[lt:Mažoji Ferma teorema]]
[[mn:Фермагийн бага теорем]]
[[nl:Kleine stelling van Fermat]]
[[pl:Małe twierdzenie Fermata]]
[[pt:Teste de primalidade de Fermat]]
[[ro:Mica teoremă a lui Fermat]]
[[ru:Малая теорема Ферма]]
[[sk:Malá Fermatova veta]]
[[sl:Fermatov mali izrek]]
[[sr:Мала Фермаова теорема]]
[[sv:Fermats lilla sats]]
[[ta:ஃபெர்மாவின் சிறிய தேற்றம்]]
[[th:ทฤษฎีบทเล็กของแฟร์มาต์]]
[[tr:Fermat'nın küçük teoremi]]
[[vi:Định lý nhỏ Fermat]]
[[zh:费马小定理]]

Поточна версія на 16:36, 6 березня 2023

Мала теорема Ферма — одне з основних тверджень елементарної теорії чисел. Вперше була сформульована в листі французького математика П'єра де Ферма до свого друга Френікля де Бессі[en] 18 жовтня 1640 року. В листі проте не було наведено доведення. Перше відоме доведення подане Лейбніцом у неопублікованих рукописах.

Формулювання

[ред. | ред. код]

Мала теорема Ферма допускає кілька еквівалентних формулювань.

Нехай  — просте,  — ціле, що не ділиться на . Тоді:

.

Еквівалентним є наступне твердження: Нехай  — просте,  — довільне ціле число. Тоді:

.

Узагальнення 1

[ред. | ред. код]

Ейлером було доведено, що для довільного взаємно простого з виконується наступне:

де  — функція Ейлера.

Узагальнення 2

[ред. | ред. код]

Рівність справедлива для всіх елементів скінченного поля , утвореного елементами.

Доведення

[ред. | ред. код]

Позначимо, як звично

 — біноміальний коефіцієнт.

Тоді для простого і маємо, що ділиться на . Справді можна записати де . Оскільки і є взаємно-простими, то, очевидно, що ділить і, як наслідок ділиться на . Твердження Малої теореми Ферма доводитимемо методом математичної індукції. Теорема очевидно справедлива для . Припустимо, що вона справджується для певного цілого . Згідно з формулою бінома Ньютона, використовуючи раніше доведене і припущення індукції одержуємо:

.

тобто , що доводить твердження для додатних цілих. Для від'ємних доведення аналогічне.

Доведення 2 (використовуючи лишки)

[ред. | ред. код]

Припустимо, що додатне число, що не ділиться на . Якщо записати

і обрахувати одержану послідовність за модулем , то ми отримаємо деяку перестановку чисел:

.

Справді, жодне з чисел не ділиться на , оскільки і і будь-яке з чисел є взаємно прості з . Далі всі числа мають бути відмінними одне від одного за модулем . Справді, якщо

де і належать множині чисел то, зважаючи на взаємну простоту і отримуємо:

, що неможливо.

Відповідно, якщо ми перемножимо обидві послідовності, то результати повинні бути еквівалентні за модулем :

Після перестановки множників і перепозначення отримуємо:

Остаточно, зважаючи, що і взаємно-прості одержуємо твердження теореми:

Припустимо, що ми маємо намистинки різних кольорів і нам потрібно зробити з них намисто довжиною намистинок. Для початку зробимо стрічку з намистинок. Існує різних стрічок. Відкинемо всі однотонні стрічки їх всього . Залишається різних стрічок. З'єднаємо початок кожної стрічки з її кінцем. Тепер деякі намиста стали однаковими, якщо їх повернути. Оскільки існує різних циклічних перестановок то існує різних намист. Виходячи з інтерпретації числа воно ціле.

Див. також

[ред. | ред. код]

Джерела

[ред. | ред. код]
  • Ойстин Оре (2003). Приглашение в теорию чисел. Москва: Едиториал УРСС. ISBN 5-354-00252-4.
  • Arthur Engel (1997). Problem-Solving Strategies. New York: Springer-Verlag. ISBN 0-387-98219-1.