Ферманың кіші теоремасы

Ферманың кіші теоремасы — сандар теориясының классикалық теоремасы былай дейді:

Егер p — және a p-ға бөлінбесе, онда a ^{p — 1}1 (mod p)  (немесе a ^{p — 1} — 1 p-ға бөлінеді).

Басқаша тұжырымдасақ,

Кез келген жәй p мен бүтін a үшін a ^p — a p-ға бөлінеді.

Дәлелдеуі

Кез келген жәй p және бүтін теріс емес a үшін ${\displaystyle a^{p}-a}$ p-ға бөлінетіндігін көрсетейік. a бойынша индукциямен дәлелдейік.

Негізі a=0 үшін ${\displaystyle a^{p}-a=0}$ p-ға бөлінеді.

Көшу. Тұжырым a=k үшін орындалсын. a=k+1 үшін дәлелдейік.

${\displaystyle a^{p}-a=(k+1)^{p}-(k+1)=k^{p}+1+\sum _{l=1}^{p-1}{p \choose l}k^{l}-k-1=}$

${\displaystyle =k^{p}-k+\sum _{l=1}^{p-1}k^{l}{p \choose l}}$

Бірақ ${\displaystyle k^{p}-k}$ p-ға индукция жорамалы бойыншы бөлінеді. Басқа қосылғыштарды айтсақ, онда ${\displaystyle {p \choose l}={p! \over l!(p-l)!}}$. ${\displaystyle 1\leq l\leq p-1}$ үшін, осы бөлшектің алымы p-ға бөлінеді, ал бөлімі — бөлінбейді, олай болса, ${\displaystyle {p \choose l}}$ ${\displaystyle p}$-ға бөлінеді. Сондықтан барлық қосылғыштар ${\displaystyle k^{p}-k+\sum _{l=1}^{p-1}{p \choose l}}$ p-ға бөлінеді.

Теріс a және тақ p үшін теореманы b=-a деп қойып оңай дәлелдейді. Теріс a мен p=2 үшін теореманың растығы ${\displaystyle a^{2}-a=a(a-1)}$ екендігінен шығады. Дәлелдеу керектігі де осы.

Теорема жалпыламасы

• Теореманың аздаған жалпыламасы мынадай: егер p жәй сан болса, ал m мен n — ${\displaystyle m\equiv n{\pmod {p-1}}}$ болатындай оң бүтін сандар болса, ${\displaystyle a^{m}\equiv a^{n}{\pmod {p}}\quad \forall a\in \mathbb {Z} }$. Осы түрде теорема ашық кілтті шифрлеу жүйесінде пайдаланылады.

• Ферманың кіші теоремасы жекеше түрі, ал Эйлер теоремасының өзі мен теоремаларының жекеше түрі болып табылады.

• Ферманың кіші теоремасы теориясында да жалпыламасы бар.

Тағы қараңыз

• Ферманың Ұлы теоремасы