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

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

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

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

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

Дәлелдеуі

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

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

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

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

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

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

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

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

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

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

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

Тағы қараңыз

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