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

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

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

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

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

Кез келген жәй p мен бүтін 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 мен nm\equiv n\pmod{p-1} болатындай оң бүтін сандар болса, a^m\equiv a^n\pmod{p} \quad\forall a\in\mathbb{Z}. Осы түрде теорема ашық кілтті шифрлеу RSA жүйесінде пайдаланылады.
  • Ферманың кіші теоремасы шекті өрістер теориясында да жалпыламасы бар.

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