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

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

Егер 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 \le l \le 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 жүйесінде пайдаланылады.

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

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

Тағы қараңыз

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