Мала теорема Ферма: відмінності між версіями
[неперевірена версія] | [перевірена версія] |
Немає опису редагування |
м Cat-a-lot: Moving from Category:Математичні теореми to Category:Теореми в теорії чисел за допомогою Cat-a-lot |
||
(Не показані 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> — [[просте число|просте]], <math>\ a</math> — довільне [[ціле число]]. Тоді: |
||
Нехай <math>\ p</math> — [[просте число|просте]], <math>\ a</math> — довільне [[ціле число|ціле]] число. Тоді: |
|||
: <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> — [[біноміальний коефіцієнт]]. |
: <math>{p \choose k} = \frac{p(p-1)(p-2)\cdots (p-k+1)}{k!} </math> — [[біноміальний коефіцієнт]]. |
||
Тоді для простого <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>\ 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, |
||
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> воно ціле. |
||
== |
== Див. також == |
||
* [[Число Кармайкла|Числа Кармайкла]] — псевдопрості числа |
|||
* [[Теорема Ферма]] |
* [[Теорема Ферма]] |
||
* [[Теорема Ферма (велика)]] |
* [[Теорема Ферма (велика)]] |
||
== Джерела == |
== Джерела == |
||
* {{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 (за методом математичної індукції)
[ред. | ред. код]Позначимо, як звично
Тоді для простого і маємо, що ділиться на . Справді можна записати де . Оскільки і є взаємно-простими, то, очевидно, що ділить і, як наслідок ділиться на . Твердження Малої теореми Ферма доводитимемо методом математичної індукції. Теорема очевидно справедлива для . Припустимо, що вона справджується для певного цілого . Згідно з формулою бінома Ньютона, використовуючи раніше доведене і припущення індукції одержуємо:
- .
тобто , що доводить твердження для додатних цілих. Для від'ємних доведення аналогічне.
Припустимо, що додатне число, що не ділиться на . Якщо записати
і обрахувати одержану послідовність за модулем , то ми отримаємо деяку перестановку чисел:
- .
Справді, жодне з чисел не ділиться на , оскільки і і будь-яке з чисел є взаємно прості з . Далі всі числа мають бути відмінними одне від одного за модулем . Справді, якщо
де і належать множині чисел то, зважаючи на взаємну простоту і отримуємо:
- , що неможливо.
Відповідно, якщо ми перемножимо обидві послідовності, то результати повинні бути еквівалентні за модулем :
Після перестановки множників і перепозначення отримуємо:
Остаточно, зважаючи, що і взаємно-прості одержуємо твердження теореми:
Доведення 3 (комбінаторне)
[ред. | ред. код]Припустимо, що ми маємо намистинки різних кольорів і нам потрібно зробити з них намисто довжиною намистинок. Для початку зробимо стрічку з намистинок. Існує різних стрічок. Відкинемо всі однотонні стрічки їх всього . Залишається різних стрічок. З'єднаємо початок кожної стрічки з її кінцем. Тепер деякі намиста стали однаковими, якщо їх повернути. Оскільки існує різних циклічних перестановок то існує різних намист. Виходячи з інтерпретації числа воно ціле.
- Числа Кармайкла — псевдопрості числа
- Теорема Ферма
- Теорема Ферма (велика)
- Ойстин Оре (2003). Приглашение в теорию чисел. Москва: Едиториал УРСС. ISBN 5-354-00252-4.
- Arthur Engel (1997). Problem-Solving Strategies. New York: Springer-Verlag. ISBN 0-387-98219-1.