Мала Фермаова теорема

Мала Фермаова теорема (не е иста со Последната Фермаова теорема) — теорема што тврди дека ако p е прост број, тогаш секој цел број a, $(a^{p}-a)$ ќе биде делив со p. Ова може да се изрази во нотација на модуларната аритметика на следниот начин:

a^{p}\equiv a{\pmod {p}}\,\!

Постои и варијанта на оваа теорема искажана на следниов начин: ако p е прост и a е цел број заемно прост со p, тогаш $(a^{p-1}-1)$ ќе биде делив со p. Запишано во модуларна аритметика:

a^{p-1}\equiv 1{\pmod {p}}\,\!

Друг начин да се изрази ова е дека ако p е прост број, и a е кој било цел број што не е делив со p, тогаш на a на степен p-1 дава остаток од 1 кога ќе се подели со p.^[1]

Малата Фермаова теорема е основа на Фермаовиот тест за прости броеви.

Примери

4 ³ − 4 = 60 е делив со 3.
7 ² − 7 = 42 е делив со 2.
( − 3) ⁷ − ( − 3) = − (2 184) е делив со 7.
2 ⁹⁷ − 2 = 158 456 325 028 528 675 187 087 900 670 е делив со 97.

Доказ

Ферма ја објаснил оваа теорема без доказ. Прв што дал доказ бил Готфрид Лајбниц, во ракопис без датум, каде што напишал дека го знаел доказот пред 1683 година.

Обопштувања

Едноставно обопштување на оваа теорема што непосредно произлегува од неа е: ако p е прост број и ако m и n се позитивни цели броеви, и $m\equiv n{\pmod {p-1}}\,$ , тогаш $a^{m}\equiv a^{n}{\pmod {p}}\quad \forall a\in \mathbb {Z}$ . Во овој облик, теоремата се користи за да се оправда методот на шифрирање RSA со јавен клуч.

Малата Фермаова теорема може да се обопшти со помош на Ојлеровата теорема: за секој модуло n и секој цел број a заемно прост со n, важи:

a^{\varphi (n)}\equiv 1{\pmod {n}}

каде φ (n) ја означува Ојлеровата φ функција што го дава бројот на цели броеви помеѓу 1 и n кои се меѓусебно прости со n. Ова е навистина обопштување, бидејќи ако n = p е прост, тогаш φ(p) = p − 1.

Ова може дополнително да се обопшти во Кармајкловата теорема.

Малата Фермаова теорема исто така има обопштување во конечните полиња.

Од малата Фермаова теорема следи Ханамовата лема, каде е кој било прост број.

Поврзано

Последна Фермаова теорема

Наводи

Литература

Paulo Ribenboim (1995). The New Book of Prime Number Records (3rd ed.). New York: Springer-Verlag. ISBN 978-0-387-94457-9.
Јанош Бољај и псевдопрости броеви (на унгарски)

[1]

Search