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

Уикипедия — ашық энциклопедиясынан алынған мәлімет
Мұнда ауысу: шарлау, іздеу

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

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

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