Ферманың кіші теоремасы
Ферманың кіші теоремасы — сандар теориясының классикалық теоремасы былай дейді:
Егер p — жәй сан және a p-ға бөлінбесе, онда a p — 1 ≡ 1 (mod p) (немесе a p — 1 — 1 p-ға бөлінеді).
Басқаша тұжырымдасақ,
Кез келген жәй p мен бүтін a үшін a p — a p-ға бөлінеді.
Дәлелдеуі
[өңдеу | қайнарын өңдеу]Кез келген жәй p және бүтін теріс емес a үшін p-ға бөлінетіндігін көрсетейік. a бойынша индукциямен дәлелдейік.
Негізі a=0 үшін p-ға бөлінеді.
Көшу. Тұжырым a=k үшін орындалсын. a=k+1 үшін дәлелдейік.
Бірақ p-ға индукция жорамалы бойыншы бөлінеді. Басқа қосылғыштарды айтсақ, онда . үшін, осы бөлшектің алымы p-ға бөлінеді, ал бөлімі — бөлінбейді, олай болса, -ға бөлінеді. Сондықтан барлық қосылғыштар p-ға бөлінеді.
Теріс a және тақ p үшін теореманы b=-a деп қойып оңай дәлелдейді. Теріс a мен p=2 үшін теореманың растығы екендігінен шығады. Дәлелдеу керектігі де осы.
Теорема жалпыламасы
[өңдеу | қайнарын өңдеу]- Теореманың аздаған жалпыламасы мынадай: егер p жәй сан болса, ал m мен n — болатындай оң бүтін сандар болса, . Осы түрде теорема ашық кілтті шифрлеу RSA жүйесінде пайдаланылады.
- Ферманың кіші теоремасы Эйлер теоремасының жекеше түрі, ал Эйлер теоремасының өзі Кармайкл мен Лагранж теоремаларының жекеше түрі болып табылады.
- Ферманың кіші теоремасы шекті өрістер теориясында да жалпыламасы бар.