Хэрэглэгч:Luckyzoloo

Фермагийн бага теорем

Pierre de Fermat –ийн бусад томьёнуудыг Fermat-ийн томъёнуудаас харж болно. Ямар нэгэн а бүхэл тоог P гэсэн анхны тоогоор зэрэг дэвшүүлэхэд P зэрэг нь аpзэргээс a хасаад гарсан тоог 2 тооны үржвэрт задлахад гарах анхны тоотой тэнцүү байдаг. Үүнийг модулиар арифметикаар бичвэл :

$a^{p}\equiv a{\pmod {p}}.$

Жишээлбэл:  Хэрвээ a=2, p = 7, бол 27 = 128 бөгөөд 128 − 2 = 7 × 18 эндээс 7 бол зэрэг нь юм.
Хэрэвээ p-д хуваагдахгүй бол Ферматын теормын дагуу a ^p − 1 − 1

$a^{p-1}\equiv 1{\pmod {p}}.$

Жишээлбэл:  Хэрвээ a=2, p = 7 бол26 = 64, and 64 − 1 = 63 = 7 × 9.
Фермагийн бага теорем бол Fermat primality шалгалт болон бага тооны онолын үр дүнгийнүндэс юм. 1640 онд Pierre de Fermat –ийн зааснаар түүний нэрээр нэрлэдэг болсон ба энэ теормыг Фермагийн их теормоос ялгахын тулд “бага теорм ” гэж нэрлэдэг.

Түүх

Pierre de Fermat

Pierre de Fermat анх 1640 оны арван сарын 18нд захидалдаа даараах байдлаар бичсэнийг түүний найз Frenivle de bessy баталсан байдаг. p divides a ^p−1 − 1 whenever p is prime and a is coprime to p.

Ерөнхий дүрэм

Хэрвээ р анхны тоо ба m болон n нь эерэг бүхэл тоо бол $m\equiv n{\pmod {p-1}}$  болох ба бүх бүхэл тооны хувьд $a^{m}\equiv a^{n}{\pmod {p}}$ байна. Энэ нь дараахыг илтгэнэ: m нь $b(p-1)+n$ -тэй тэнцүү бол $a^{m}=a^{b(p-1)}\cdot a^{n}\equiv \left({a^{p-1}}\right)^{b}\cdot a^{n}\equiv 1^{b}\cdot a^{n}\equiv a^{n}{\pmod {p}}.$ болно. Энэ хэлбэр нь RSA public key encryption-н теоромыг зөвтгөхөд хэрэглэгдэж байна.

Фермагийн бага теоромыг Эйлерийн теоремоор дүгнэвэл: ямар нэгэн модуль n ба ямар нэгэн бүхэл тоо а ба coprime n бол  :$a^{\varphi (n)}\equiv 1{\pmod {n}}$ байна. φ(n) нь Euler's theorem: -н утгыг илэрхийлнэ. (N нь coprime нь 1-ээс N хооронд бүхэл тоо тоолох нь) Энэ бол нийтэд хэрэглэдэг дүрэм. Учир нь хэрэв n = p анхний тоо бол φ(p) = p – 1 болно. Энэ нь цаашид Carmichael's theorem болон Lagrange's theorem-г онолын хувьд нэгтгэн дүгнэсэн. Фермагийн теорем нь мөн хязгаарлагдмал оронг нэгтгэн дүгнэсэн.

Урвуу

Фермагийн бага теоромын урвуу нь ерөнхийдөө үнэн биш. Энэ нь Carmichael numbers-д бүтэлгүй Гэсэн хэдий ч теоромын бага зэрэг хүчтэй хэлбэр нь үнэн гэдэгийг Lehmer-н теоромоос мэдэж болно. Дараах теором байна:

$a^{p-1}\equiv 1{\pmod {p}}$

ба p – 1-ыг q анхны тоонд хуваавал  :$a^{(p-1)/q}\not \equiv 1{\pmod {p}}$ байна. Энд: р нь анхны тоо

Энэ теорем Лукас-Lehmer-н тест ба чухал тооны энгийн хялбар байдлын тестын үндэс суурь нь болдог.