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

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

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

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

Кез келген жәй p мен бүтін 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 жүйесінде пайдаланылады.
  • Ферманың кіші теоремасы шекті өрістер теориясында да жалпыламасы бар.

Тағы қараңыз өңдеу