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

Фермагийн бага теорем нь анхны тооны шинж чанарын тухай харуулдаг, тооны онол дахь нэг теорем юм.

Ерөнхий ойлголт

Пьер де Ферма

"p - анхны тоо, a нь p-гийн хуваагдагч биш бүхэл тоо (a ба p нь харилцан анхны тоонууд) байг. Тэгвэл

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

Өөрөөр хэлбэл a-г p-1 зэрэг дэвшүүлэхэд гарах тоог p-д хуваахад үлдэгдэл нь 1 гарна" гэдэг нь Фермагийн бага теоремын тодорхойлолт юм. Фермагийн их теоремоос ялгахын тулд "бага" гэдэг нэрийг хэрэглэдэг.

Энэхүү теорем нь Пьер де Фермагийн нэрээр нэрлэгддэг боловч түүний бусад таамаглалуудтай адилаар, Фермагийн гэх баталгаа олдоогүй. Уг теоремыг хамгийн анх Готфрид Лейбниц баталсан гэж үздэг.

Баталгаа

Хоёр гишүүнтийг зэрэг дэвшүүлэх хууль ёсоор математик индукцийн арга ашиглан батлах нь хялбар. Энд

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

буюу a-г p зэрэг дэвшүүлсэн тоог p-д хуваахад гарах үлдэгдэл нь a-г p-д хуваахад гарах үлдэгдэлтэй тэнцүү хэмээх теоремыг ашиглая.

1. (m + 1)^p -г задалбал,
   m^p + _pC₁m^p-1 + _pC₂m^p-2 + … + _pC_p-1m + 1
   болно.
2. Энд хоёр захын гишүүнээс бусад бүх гишүүнд _pC_k нь коэффициент болно. Энэ нь p нь анхны тоо бол k нь 1-ээс бага биш, p-ээс их биш бол заавал p-д хуваагдана.
3. Өөрөөр хэлбэл, хоёр захын гишүүнээс бусад нь p-д хуваагдана. Иймээс (m + 1)^p -г p-д хуваахад гарах үлдэгдэл нь m^p + 1-г p-д хуваахад гарах үлдэгдэлтэй тэнцүү болно.
4. m = 1 гэе. 2^p = (1 + 1)^p -г p-д хуваахад гарах үлдэгдэл нь 1^p + 1 = 2 болох бөгөөд энэ нь a = 2 үед Фермагийн бага теорем үнэн болохыг илтгэж байна.
5. a-гаар индукцлэе. Өөрөөр хэлбэл a = k үед теорем үнэн гэж үзье. 3-р алхам ёсоор (k + 1)^p-г p-д хуваахад гарах үлдэгдэл нь k^p + 1 -г p-д хуваахад гарах үлдэгдэлтэй тэнцүү. Цаашилбал математик индукцийн зарчим ёсоор k + 1 -г p-д хуваахад гарах үлдэгдэлтэй тэнцүү. Иймд a = k + 1 тохиолдолд ч биелж байна. Ийнхүү математик индукцийн зарчим ёсоор 2-оос бага биш бүх a-гийн хувьд теорем биелж байна.
6. a = 0, 1 үед илэрхий.

（Теорем батлагдав）

Өөр аргаар баталъя.

P- Анхны тоо

P, X харилцан анхны тоо

$x^{p-1} - 1 \equiv 0 \pmod{p}$ гэж батал

Бодолт

P, X харилцан анхны тоо учраас x, 2x, 3x ………,(p-1)x эдгээр тоонууд бүгд P-д үлдэгдэлтэй хуваагдах бөгөөд тэдгээр нь хоорондоо ялгаатай байна.

x ≡ a1 (mod P)

2x ≡ a2 (mod P)

3x ≡ a3 (mod P)

……………………..

(p-1)x ≡ a(p-1)(mod P)

x* 2x * 3x ……………(p-1)x ≡ (a1 * a2 * a3 *………………*ap-1 ) mod P

a1, ≠ a2 ≠ a3 ≠………………≠ ap-1 эдгээр тоо P-н үлдэгдэл учраас бүгд P-с бага тоо байна.

x^(p-1)*(1*2*3………(p-1)) ≡ (1*2*3*4………..(p-1)) mod P

x^(p-1)(p-1)! ≡ (p-1)! Mod P

x^(p-1) ≡ 1 ( mod P )

x^(p-1) - 1 ≡ 0 ( mod P )

(теорем батлагдав.)

Эйлерийн теорем

Хожим Леонард Эйлер тус теоремыг өргөтгөж, a ба n нь харилцан анхны бүхэл тоонууд байх үед,

$a^{\varphi(n)} \equiv 1 \pmod{n}$

тэнцэтгэл биелэхийг үзүүлсэн. Энд $\varphi(n)$ нь n-ээс их биш бөгөөд n-тэй харилцан анхны натурал тоонуудын тоог илтгэх бөгөөд Эйлерийн функц гэж нэрлэгддэг.

n нь анхны тоо гэвэл $\varphi(n)=n-1$ учраас Фермагийн теорем гарна.