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

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

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

Пьер де Ферма

"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$ учраас Фермагийн теорем гарна.

Жишээ бодолтууд

1 $f(n)=2^{n}+3^{n}+6^{n}-1$ хувьд байх гэж батал. $\forall p{\in }\mathbb {P}$
$p|f(n)$

Бодолт.

үед  байна гэдгийг харахад төвөггүй. 
 $p{\in }\mathbb {P}$

тул гэе. Тэгвэл Фермагийн бага теором ёсоор:

$f(p)=2^{p}-1+3^{p}+6^{p}-1(modp)$ 
 байна.    тул  .

2. тэгшитгэл натурал шийдгүйг батал. Бодолт

-ийг хуваадаг хамгийн бага анхны тоо  -г авч үзье. Тэгвэл  байна. Фермагийн бага теором ёсоор  , бодлогын нөхцөлөөс 

$f(n)=2^{n}+3^{n}+6^{n}-1$

      буюу   болж зөрчил үүслээ.  

4. , дараалалд хос хосоороо харилцан анхны байх төгсгөлгүй олон гишүүн байна гэж батал. Бодолт. Энэ дарааллаас гэсэн хос хосоороо харилцан анхны ширхэг тоог цуглуулсан гэж саная. Одоо бид нар гишүүнийг байгуулбал энэ алгоритмоор төгсгөлгүй олон гишүүнийг байгуулж чадна. үржвэрийн анхны тоон хуваагчдыг гэе. Фермагийн бага теором ёсоор тул энд тэгвэл болох ба бүр сондгой тул ондгой иймд болж шинэ гишүүнийг байгуулж чадсанаар төгсгөлгүй олон гишүүн байгуулж чадах нь батлагдав.

Энэ математикийн тухай өгүүлэл дутуу дулимаг бичигджээ. Нэмж гүйцээж өгөхийг хүсье.