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

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

Егер 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}(\genfrac{}{}{0ex}{}{p}{l})k^l-k-1=$

$=k^p-k+\sum _{l=1}^{p-1}{k}^l(\genfrac{}{}{0ex}{}{p}{l})$

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

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

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

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

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

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

Тағы қараңыз

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