Fermatsning kichik teoremasining dalillari - Proofs of Fermats little theorem - Wikipedia

Ushbu maqola turli xil narsalarni to'playdi dalillar ning Fermaning kichik teoremasi, deb ta'kidlaydi

har bir kishi uchun asosiy raqam p va har bir tamsayı a (qarang modulli arifmetik ).

Soddalashtirishlar

Ba'zilari Fermaning kichik teoremasining isboti quyida keltirilgan ikkita soddalashtirishga bog'liq.

Birinchisi, biz buni taxmin qilishimiz mumkin a oralig'ida 0 ≤ ap − 1. Bu qonunlarning oddiy natijasidir modulli arifmetika; biz shunchaki avval kamaytirishimiz mumkin, deb aytmoqdamiz a modulp. Bu kamaytirishga mos keladi modulp, buni tekshirish mumkin.

Ikkinchidan, buni isbotlash kifoya

uchun a oralig'ida 1 ≤ ap − 1. Haqiqatan ham, agar avvalgi tasdiqlash shunday bo'lsa a, ikkala tomonni ko'paytirib a teoremaning asl shaklini beradi,

Boshqa tomondan, agar a = 0, teorema ahamiyatsiz.

Kombinatorial dalillar

Marjonlarni sanash orqali dalil

Bu, ehtimol, eng kam matematik asosni talab qiladigan eng oddiy ma'lum bo'lgan dalil. Bu a ning jozibali namunasidir kombinatorial dalil (o'z ichiga olgan dalil ob'ektlar to'plamini ikki xil usulda hisoblash ).

Bu erda keltirilgan dalil moslashtirishdir Golomb isboti.[1]

Hamma narsani sodda qilish uchun, keling, buni taxmin qilaylik a a musbat tamsayı. Mumkin bo'lgan barcha narsalarni ko'rib chiqing torlar ning p belgilaridan foydalanib, alifbo bilan a turli xil belgilar. Bunday satrlarning umumiy soni ap, chunki u erda a har biri uchun imkoniyatlar p pozitsiyalar (qarang. qarang mahsulot qoidasi ).

Masalan, agar p = 5 va a = 2, keyin biz ikkita belgidan iborat alifbodan foydalanishimiz mumkin (aytaylik) A va B) va mavjud 25 = 32 5 uzunlikdagi iplar:

AAAAA, AAAAB, AAABA, AAABB, AABAA, AABAB, AABBA, AABBB,
ABAAA, ABAAB, ABABA, ABABB, ABBAA, ABBAB, ABBBA, ABBBB,
BAAAA, BAAAB, BAABA, BAABB, BABAA, BABAB, BABBA, BABBB,
BBAAA, BBAAB, BBABA, BBABB, BBBAA, BBBAB, BBBBA, BBBBB.

Agar biz bitta belgidan iborat qatorlarni ro'yxatdan olib tashlasak (biz misolimizda, AAAAA va BBBBB), qolganlari; qolgan apa satrlarni guruhlarga ajratish mumkin, har bir guruh to'liq o'z ichiga oladi p torlar. Bundan kelib chiqadiki apa ga bo'linadip.

Marjonlarni

Etti xil ipni ifodalaydigan marjon (ABCBAAC, BCBAACA, CBAACAB, BAACABC, AACABCB, ACABCBA, CABCBAA)
Faqat bitta ipni ifodalaydigan marjon (AAAAAAA)

Keling, har bir bunday mag'lubiyatni a ni ifodalovchi deb o'ylaymiz marjon. Ya'ni, biz ipning ikki uchini bir-biriga bog'laymiz va agar iloji bo'lsa, ikkita ipni bir xil marjon deb bilamiz aylantirmoq ikkinchi qatorni olish uchun bitta mag'lubiyat; bu holda biz ikkita satr deb aytamiz do'stlar. Bizning misolimizda quyidagi satrlar do'stdir:

AAAAB, AAABA, AABAA, ABAAA, BAAAA.

Xuddi shunday, quyidagi ro'yxatning har bir satri bitta marjonga mos keladi.

AAABB, AABBA, ABBAA, BBAAA, BAAAB,
AABAB, ABABA, BABAA, ABAAB, BAABA,
AABBB, ABBBA, BBBAA, BBAAB, BAABB,
ABABB, BABBA, ABBAB, BBABA, BABAB,
ABBBB, BBBBA, BBBAB, BBABB, BABBB,
BAAAA, AAAAB, AAABA, AABAA, ABAAA,
AAAAA,
BBBBB.

E'tibor bering, yuqoridagi ro'yxatda bir nechta belgi bo'lgan har bir marjon 5 xil ip bilan ifodalanadi va bitta ip bilan ifodalangan marjonlarni soni 2 ga teng, ya'ni alohida belgilar soni. Shunday qilib, ro'yxat nima uchun juda aniq ko'rsatilgan 32 − 2 ga bo'linadi 5.

Berilgan satrni qancha do'stga ishlashini aniqlash uchun quyidagi qoidadan foydalanish mumkin S ega:

Agar S mag'lubiyatning bir nechta nusxalaridan tashkil topgan Tva T o'z-o'zidan takrorlanadigan satrlarga bo'linib bo'lmaydi, keyin do'stlar soni S (shu jumladan S o'zi) ga teng uzunlik ning T.

Masalan, biz ipdan boshlaymiz deylik S = ABBABBABBABB, bu qisqa ipning bir nechta nusxasidan iborat T = ABB. Agar biz uni bir vaqtning o'zida bitta belgini aylantirsak, quyidagi 3 qatorni olamiz:

ABBABBABBABB,
BBABBABABABBA,
BABBABBABBAB.

Boshqalar yo'q, chunki ABB to'liq 3 ta belgidan iborat va uni takrorlanadigan satrlarga ajratib bo'lmaydi.

Dalilni to'ldirish

Yuqoridagi qoidadan foydalanib, biz Fermaning kichik teoremasining isbotini quyidagicha osonlikcha bajarishimiz mumkin. Bizning boshlang'ich hovuzimiz a p satrlarni ikkita toifaga bo'lish mumkin:

  • Ba'zi qatorlar mavjud p bir xil belgilar. To'liq bor a ulardan bittasi, alifboda har bir belgi uchun. (Bizning ishlaydigan misolimizda, bu satrlar AAAAA va BBBBB.)
  • Qolgan qatorlar alifbodan kamida ikkita alohida belgidan foydalanadilar. Agar biz ajrala olsak S ba'zi bir mag'lubiyatning takroriy nusxalariga T, uzunligi T uzunligini bo'lish kerak S. Ammo, uzunligidan S asosiy hisoblanadi p, uchun mumkin bo'lgan yagona uzunlik T ham p. Shuning uchun yuqoridagi qoida shundan dalolat beradi S aniq bor p do'stlar (shu jumladan S o'zi).

Ikkinchi toifada o'z ichiga oladi a pa torlari va ular guruhlarga bo'linishi mumkin p torlar, har bir marjon uchun bitta guruh. Shuning uchun, a pa bo'linishi kerak pva'da qilinganidek.

Dinamik tizimlardan foydalangan holda isbotlash

Ushbu dalil ba'zi bir asosiy tushunchalardan foydalanadi dinamik tizimlar.[2]

Biz oilani ko'rib chiqishdan boshlaymiz funktsiyalari Tn(x), qaerda n ≥ 2 - an tamsayı, xaritalash oraliq [0, 1] formula bo'yicha o'ziga

qayerda {y} belgisini bildiradi kasr qismi ning y. Masalan, funktsiya T3(x) quyida keltirilgan:

Tn funktsiyasiga misol

Raqam x0 deb aytilgan a sobit nuqta funktsiya f(x) agar f(x0) = x0; boshqacha qilib aytganda, agar f barglar x0 sobit. Funksiyaning sobit nuqtalarini grafik jihatdan osongina topish mumkin: ular shunchaki x nuqtalari koordinatalari grafik ning f(x) chiziq grafigini kesib o'tadi y = x. Masalan, funktsiyaning sobit nuqtalari T3(x) 0, 1/2 va 1; ular quyidagi diagrammada qora doiralar bilan belgilanadi:

Tn funktsiyasining sobit nuqtalari

Bizga quyidagi ikkita lemma kerak bo'ladi.

Lemma 1. Har qanday kishi uchun n ≥ 2, funktsiyasi Tn(x) aniq bor n sobit nuqtalar.

Isbot. Yuqoridagi rasmda 3 ta aniq nuqta bor va bir xil geometrik dalillar har qandayida qo'llaniladi n ≥ 2.

Lemma 2. Har qanday musbat tamsayılar uchun n va mva har qanday 0-x-1,

Boshqa so'zlar bilan aytganda, Tmn(x) bo'ladi tarkibi ning Tn(x) va Tm(x).

Isbot. Ushbu lemmaning isboti qiyin emas, lekin biz so'nggi nuqta bilan biroz ehtiyot bo'lishimiz kerak x = 1. Bu nuqta uchun lemma aniq, chunki

Shunday qilib, 0 ≤ deb taxmin qilaylik x <1. Bunday holda,

shunday Tm(Tn(x)) tomonidan berilgan

Shuning uchun, biz nimani ko'rsatishimiz kerakligi shundan iborat

Buning uchun biz {nx} = nxk, qayerda k bo'ladi butun qism ning nx; keyin

beri mk butun son

Endi funktsiyani o'rganish orqali Fermaning kichik teoremasini isbotlashni to'g'ri boshlaylik Tap(x). Biz buni taxmin qilamiz a ≥ 2. Lemma 1 dan biz buni bilamiz ap sobit nuqtalar. Lemma 2 tomonidan biz buni bilamiz

shuning uchun har qanday sobit nuqta Ta(x) avtomatik ravishda belgilangan nuqtadir Tap(x).

Bizni belgilangan nuqtalari qiziqtiradi Tap(x) bu emas ning sobit nuqtalari Ta(x). Keling, bunday fikrlar to'plamini chaqiramiz S. Lar bor apa ball S, chunki yana Lemma 1 tomonidan, Ta(x) aniq bor a sobit nuqtalar. Quyidagi diagramma vaziyatni aks ettiradi a = 3 va p = 2. Qora doiralar - ning nuqtalari S, ulardan 3 tasi mavjud2 − 3 = 6.

S to'plamidagi sobit nuqtalar

Dalilning asosiy g'oyasi endi to'plamni ajratishdir S uning ichiga orbitalar ostida Ta. Buning ma'nosi shundaki, biz bir nuqtani tanlaymiz x0 yilda Sva takroran murojaat qiling Ta(x) unga, ballar ketma-ketligini olish uchun

Ushbu ketma-ketlik orbitasi deb ataladi x0 ostida Ta. Lemma 2 tomonidan ushbu ketma-ketlikni qayta yozish mumkin

Biz buni taxmin qilayotganimiz uchun x0 ning sobit nuqtasidir Ta p(x), keyin p biz bosgan qadamlar Tap(x0) = x0, va shu paytdan boshlab ketma-ketlik takrorlanadi.

Biroq, ketma-ketlik qila olmaydi undan oldinroq takrorlashni boshlang. Agar shunday bo'lsa, takrorlanadigan qismning bo'linishi bo'lishi kerak edi p, shuning uchun u 1 bo'lishi kerak edi (beri p asosiy). Ammo bu bizning taxminimizga ziddir x0 ning sobit nuqtasi emas Ta.

Boshqacha qilib aytganda, orbitada to'liq mavjud p aniq fikrlar. Bu har bir orbitaga to'g'ri keladi S. Shuning uchun, to'plam So'z ichiga oladi ap − a har biri o'z ichiga olgan orbitalarga bo'linishi mumkin p ball, shuning uchun ap − a ga bo'linadi p.

(Ushbu dalil aslida xuddi shunday marjonlarni hisoblash uchun dalil Yuqorida keltirilgan, shunchaki boshqa ob'ektiv orqali ko'rib chiqilgan: bazani raqamlar ketma-ketligi bilan berilgan [0, 1] oralig'i haqida o'ylash mumkin a (0 va 1 orasidagi farqimiz, ".0000 ..." va ".9999 ..." bilan tugaydigan butun sonlarni ifodalash o'rtasidagi tanish farqga to'g'ri keladi). Tan bunday ketma-ketlikni almashtirishga teng n ko'p raqamlar. Buning sobit nuqtalari davr taqsimoti bilan tsiklik bo'lgan ketma-ketliklar bo'ladi n. Xususan, ning belgilangan nuqtalari Tap uzunlikdagi marjonlarni deb hisoblash mumkin p, bilan Tan tomonidan bunday marjonlarni aylanishiga mos keladi n dog'lar.

Ushbu dalilni 0 dan 1 gacha ajratmasdan, shunchaki yarim ochiq oraliqdan foydalanib taqdim etish mumkin edi [0, 1); keyin Tn faqat bo'lar edi n - 1 sobit nuqta, lekin TapTa hali ham ishlaydi apa, agar kerak bo'lsa.)

Ko'p pulli dalillar

Binomial teoremadan foydalangan holda isbotlash

Buning tasdig'i Eyler,[3] foydalanadi induksiya barcha butun sonlar uchun teoremani isbotlash a ≥ 0.

Asosiy qadam, bu 0p ≡ 0 (modp), ahamiyatsiz. Keyinchalik, agar teorema to'g'ri bo'lsa, buni ko'rsatishimiz kerak a = k, keyin bu ham to'g'ri a = k + 1. Ushbu induktiv qadam uchun bizga quyidagi lemma kerak.

Lemma. Har qanday butun sonlar uchun x va y va har qanday eng yaxshi uchun p, (x + y)p ≡ xp + yp (modp).

Lemma birinchi kurs talabasi. Keyinchalik dalilni qoldirib, indüksiyani davom ettiramiz.

Isbot. Faraz qiling kpk (mod p) va ko'rib chiqing (k+1)p. Bizda lemma bor

Induksiya gipotezasidan foydalangan holda, biz bunga egamiz kpk (mod p); va, ahamiyatsiz, 1p = 1. Shunday qilib

bu teoremaning bayoni a = k+1. ∎

Lemmani isbotlash uchun bizni kiritishimiz kerak binomiya teoremasi, bu har qanday musbat tamsayı uchun ekanligini bildiradi n,

bu erda koeffitsientlar binomial koeffitsientlar,

jihatidan tavsiflangan faktorial funktsiyasi, n! = 1×2×3×⋯×n.

Lemmaning isboti. Ikkilamchi koeffitsientni eksponent asosiy darajaga teng deb hisoblaymiz p:

Binomial koeffitsientlarning barchasi butun sonlardir. Numerator koeffitsientni o'z ichiga oladi p faktorial ta'rifi bo'yicha. 0 men < p, maxrajdagi atamalarning ikkalasi ham faktorni o'z ichiga olmaydi p (ning ustunligiga tayanib p), koeffitsientning o'zi asosiy omilga ega bo'lish uchun qoldiriladi p raqamdan, shuni anglatuvchi

Modulo p, bu binomiya teoremasining o'ng tomonidagi yig'indining birinchi va oxirgi shartlaridan boshqa hamma narsani yo'q qiladi p. ∎

Ning ustunligi p lemma uchun juda muhimdir; aks holda, bizda shunga o'xshash misollar mavjud

bu 4 ga bo'linmaydi.

Multinomial kengayish yordamida tasdiqlash

Birinchi marta kashf etilgan dalil Leybnits (kim nashr etmagan)[4] va keyinchalik tomonidan qayta kashf etilgan Eyler,[3] ning juda oddiy qo'llanmasi multinomial teorema bu erda soddalik uchun olib kelingan.

Summa salbiy bo'lmagan butun indekslarning barcha ketma-ketliklari bo'yicha olinadi k1 orqali km barchasi yig'indisi kmen bu n.

Shunday qilib ifoda etsak a 1s (bir) yig'indisi sifatida biz olamiz

Shubhasiz, agar p asosiy va agar bo'lsa kj ga teng emas p har qanday kishi uchun j, bizda ... bor

va

agar kj ga teng p kimdir uchun j.

To'liq borligi sababli a shunday elementlar kj = p, teorema quyidagicha.

(Ushbu dalil, asosan, ning qo'polroq variantidir marjonlarni hisoblash uchun dalil ilgari berilgan; multinomial koeffitsientlar mag'lubiyatni o'zboshimchalik bilan anagrammalarga almashtirish usullarini hisoblaydi, marjonlarni argumenti esa simlarni tsiklik anagrammalarga aylantirish usullarini hisoblaydi. Ya'ni, bu erda noan'anaviy juda ko'p koeffitsientlar bo'linadi p uzunlikdagi har bir noan'anaviy marjonlarni natijasi sifatida ko'rish mumkin p qatoriga o'ralgan bo'lishi mumkin p ko'p usullar.

Ushbu multinomial kengayish, albatta, asosini tashkil etadigan narsa binomial teoremaga asoslangan isbot yuqorida)

Quvvat mahsulotining kengayishidan foydalangan holda isbotlash

Rasmiy energiya mahsulotlarini kengaytirishga asoslangan qo'shimcha-kombinatorial dalil Giedrius Alkauskas tomonidan berilgan.[5] Ushbu dalil ikkalasini ham ishlatmaydi Evklid algoritmi na binomiya teoremasi, aksincha u ishlaydi rasmiy quvvat seriyalari ratsional koeffitsientlar bilan.

Eyler teoremasining alohida hodisasi sifatida isbot

Ushbu dalil,[3][6] tomonidan kashf etilgan Jeyms Fil suyagi[7] tomonidan qayta kashf etilgan Dirichlet[8] ba'zi bir fonni talab qiladi modulli arifmetik.

Keling, buni taxmin qilaylik a ijobiy va bo'linmaydigan p.G'oya shundaki, agar biz raqamlar ketma-ketligini yozsak

 

 

 

 

(A)

va har bir modulni kamaytiring p, natijada ketma-ketlikning qayta tashkil etilishi bo'lib chiqadi

 

 

 

 

(B)

Shuning uchun har bir ketma-ketlikdagi sonlarni ko'paytirsak, natijalar bir xil modul bo'lishi kerak p:

Birgalikda yig'ish a atamalar hosil beradi

Nihoyat, biz raqamlarni "bekor qilishimiz" mumkin 1, 2, ..., p − 1 olish, ushbu tenglamaning har ikki tomonidan

Yuqorida keltirilgan dalillarda biz oqlashimiz kerak bo'lgan ikkita qadam mavjud:

  • Nima uchun ketma-ketlik elementlari (A), qisqartirilgan modul p, (ning qayta tashkil etilishiB) va
  • Modulli arifmetikani sozlashda nima uchun "bekor qilish" haqiqiydir.

Biz bularni quyida isbotlaymiz; avval ushbu dalilning misolini amalda ko'rib chiqaylik.

Misol

Agar a = 3 va p = 7, keyin ko'rib chiqilayotgan ketma-ketlik

7 modulini kamaytirish

bu faqat qayta tashkil etish

Ularni ko'paytirish beradi

anavi,

1 × 2 × 3 × 4 × 5 × 6 hosilalarini bekor qilish

bu Fermaning kichik teoremasi a = 3 vap = 7.

Bekor qilish to'g'risidagi qonun

Keling, nima uchun ba'zi holatlarda "bekor qilish" haqiqiyligini tushuntirib beraylik. To'liq bayonot quyidagicha. Agar siz, xvay butun sonlar va siz oddiy songa bo'linmaydi pva agar bo'lsa

 

 

 

 

(C)

unda biz "bekor qilishimiz" mumkin siz olish

 

 

 

 

(D.)

Bizning foydalanishimiz bekor qilish to'g'risidagi qonun yuqoridagi Fermaning kichik teoremasining isboti haqiqiy edi, chunki raqamlar 1, 2, ..., p − 1 albatta bo'linmaydi p (haqiqatan ham ular kichikroq dan p).

Biz bekor qilish to'g'risidagi qonunni osongina isbotlashimiz mumkin Evklid lemmasi, odatda, agar u asosiy bo'lsa p mahsulotni ajratadi ab (qayerda a va b tamsayılar), keyin p bo'linishi kerak a yoki b. Darhaqiqat, tasdiqlash (C) shunchaki buni anglatadi p ajratadi uxuy = siz(xy). Beri p bo'linmaydigan asosiy darajadir siz, Evklid lemmasi bizni ajratish kerakligini aytadi x − y o'rniga; anavi, (D.) ushlab turadi.

E'tibor bering, bekor qilish to'g'risidagi qonun amal qiladigan shartlar juda qattiq va shuning uchun Fermaning kichik teoremasi buni talab qiladi p asosiy hisoblanadi. Masalan, 2 × 2 ≡ 2 × 5 (mod 6), lekin bu to'g'ri emas 2 ≡ 5 (mod 6). Biroq, bekor qilish qonunining quyidagi umumlashtirilishi amal qiladi: agar siz, x, yva z agar butun sonlar bo'lsa siz va z bor nisbatan asosiy va agar bo'lsa

unda biz "bekor qilishimiz" mumkin siz olish

Bu a Evklid lemmasining umumlashtirilishi.

Qayta tartibga solish xususiyati

Nihoyat, nima uchun ketma-ketligini tushuntirishimiz kerak

modul kamaytirilganda p, ketma-ketlikni qayta tashkil etishga aylanadi

Birinchidan, shartlarning hech biri a, 2a, ..., (p − 1)a nol modulga mos kelishi mumkin p, agar shunday bo'lsa k raqamlardan biridir 1, 2, ..., p − 1, keyin k bilan nisbatan asosiy hisoblanadi p, va shunday a, shuning uchun Evklid lemmasi bizga buni aytadi ka aktsiyalar hech qanday omilga ega emas p. Shuning uchun, hech bo'lmaganda biz raqamlar ekanligini bilamiz a, 2a, ..., (p − 1)a, modul kamaytirilganda p, raqamlar orasida bo'lishi kerak 1, 2, 3, ..., p − 1.

Bundan tashqari, raqamlar a, 2a, ..., (p − 1)a barchasi bo'lishi kerak aniq ularni modul bilan kamaytirgandan so'ng p, chunki agar

qayerda k va m biri 1, 2, ..., p − 1, keyin bekor qilish to'g'risidagi qonun bizga buni aytadi

Ikkalasidan beri k va m o'rtasida 1 va p − 1, ular teng bo'lishi kerak. Shuning uchun, shartlar a, 2a, ..., (p − 1)a modul kamaytirilganda p aniq bo'lishi kerak. Xulosa qilish uchun: ni kamaytirganda p − 1 raqamlar a, 2a, ..., (p − 1)a modul p, biz ketma-ketlikning alohida a'zolarini olamiz 12, ..., p − 1. To'liq borligi sababli p − 1 Ulardan birinchisi, ikkinchisining qayta tuzilishi bo'lishi mumkin bo'lgan yagona imkoniyat.

Eyler teoremasiga arizalar

Ushbu usulni isbotlash uchun ham ishlatish mumkin Eyler teoremasi, raqamlari biroz o'zgargan holda 1 ga p − 1 dan kam sonlar bilan almashtiriladi va ba'zi sonlar bilan koprime qilinadi m (albatta asosiy emas). Qayta tuzish xususiyati ham, bekor qilish qonuni ham (aytib o'tilgan umumlashtirilgan shakl bo'yicha) yuqorida ) hali ham mamnun va ulardan foydalanish mumkin.

Masalan, agar m = 10, keyin raqamlar kamroqm va bilan nusxalash m bor 1, 3, 7va 9. Shunday qilib, bizda:

Shuning uchun,

Eyler mezonining xulosasi sifatida isbot

Guruh nazariyasidan foydalangan holda dalillar

Standart dalil

Bu dalil[9] ning eng asosiy elementlarini talab qiladi guruh nazariyasi.

G'oya bu to'plamni tan olishdir G = {1, 2, …, p − 1}, ko'paytirish amalida (modul olingan) p) hosil qiladi guruh. Tekshirish uchun biroz kuch talab qiladigan yagona guruh aksiomasi bu har bir element G qaytarib bo'lmaydigan. Buni bir lahzaga ishonch bilan qabul qilib, shunday deb taxmin qilaylik a oralig'ida 1 ≤ ap − 1, anavi, a ning elementidir G. Ruxsat bering k bo'lishi buyurtma ning a, anavi, k eng kichik musbat butun sonidir ak ≡ 1 (mod.)p). Keyin raqamlar 1, a, a2, ..., ak −1 qisqartirilgan modulp shakl kichik guruh ningG kimning buyurtma buk va shuning uchun, tomonidan Lagranj teoremasi, k tartibini ajratadi G, bu p − 1. Shunday qilib p − 1 = km ba'zi bir musbat tamsayı uchun m undan keyin

Buni har bir element isbotlash uchun b ning G teskari, biz quyidagicha harakat qilishimiz mumkin. Birinchidan, b bu koprime ga p. Shunday qilib Bézout kimligi bizni butun sonlar borligiga ishontiradi x va y shu kabi bx + py = 1. Ushbu tenglik modulini o'qish p, biz buni ko'ramiz x uchun teskari b, beri bx ≡ 1 (mod.)p). Shuning uchun, ning har bir elementi G qaytarib bo'lmaydigan. Shunday qilib, ilgari ta'kidlanganidek, G guruhdir.

Masalan, qachon p = 11, har bir elementning teskari tomonlari quyidagicha berilgan:

a12345678910
a −116439287510

Eylerning isboti

Agar biz avvalgi dalilni olsak va Lagranj teoremasidan foydalanish o'rniga uni shu o'ziga xos vaziyatda isbotlashga harakat qilsak, u holda biz Eylerning uchinchi dalilini olamiz, ya'ni u tabiiyroq deb topdi.[10][11] Ruxsat bering A elementlari raqamlar bo'lgan to'plam bo'ling 1, a, a2, ..., ak − 1 qisqartirilgan modulp. Agar A = G, keyin k = p − 1 va shuning uchun k ajratadi p −1. Aks holda, ba'zilari bor b1 ∈ G\A.

Ruxsat bering A1 elementlari raqamlar bo'lgan to'plam bo'ling b1, ab1, a2b1, …, ak − 1b1 qisqartirilgan modulp. Keyin A1 bor k aniq elementlar, chunki aks holda ikkita aniq raqam bo'ladi m, n ∈ {0, 1, ..., k − 1} shu kabi amb1anb1 (mod p), bu mumkin emas, chunki u bunga ergashadi aman (mod p). Boshqa tomondan, ning elementi yo'q A1 ning elementi bo'lishi mumkin A, chunki aks holda raqamlar bo'lar edi m, n ∈ {0, 1, …, k − 1} shu kabi amb1an (mod p), undan keyin b1anakman + km (mod p), bu imkonsiz, chunki b1A.

Shunday qilib, to'plam AA1 bor 2k elementlar. Agar u teng bo'lib chiqsaG, keyin 2k = p −1 va shuning uchun k ajratadi p −1. Aks holda, ba'zilari bor b2 ∈ G\(AA1) va biz hamma narsani qayta boshlashimiz mumkin A2 elementlari raqamlar bo'lgan to'plam sifatida b2, ab2, a2b2, ..., ak − 1b2 qisqartirilgan modulp. Beri G cheklangan, bu jarayon bir nuqtada to'xtashi kerak va bu buni tasdiqlaydi k ajratadi p − 1.

Masalan, agar a = 5 va p = 13, keyin, beri

  • 52 = 25 ≡ 12 (mod 13),
  • 53 = 125 ≡ 8 (mod 13),
  • 54 = 625-1 (mod 13),

bizda ... bor k = 4 va A = {1, 5, 8, 12}. Shubhasiz, A ≠ G = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}. Ruxsat bering b1 ning elementi bo'lishi G\A; masalan, oling b1 = 2. Keyin, beri

  • 2×1 = 2,
  • 2×5 = 10,
  • 2 × 8 = 16-3 (mod 13),
  • 2 × 12 = 24-11 (mod 13),

bizda ... bor A1 = {2, 3, 10, 11}. Shubhasiz, AA1G. Ruxsat bering b2 ning elementi bo'lishi G\(AA1); masalan, oling b2 = 4. Keyin, beri

  • 4×1 = 4,
  • 4 × 5 = 20 ≡ 7 (mod 13),
  • 4 × 8 = 32-6 (mod 13),
  • 4 × 12 = 48-9 (mod 13),

bizda ... bor A2 = {4, 6, 7, 9}. Va hozir G = AA1A2.

To'plamlarga e'tibor bering A, A1va shunga o'xshash narsalar aslida kosets ning A yilda G.

Izohlar

  1. ^ Golomb, Sulaymon V. (1956), "Fermaning" Kichkina "teoremasini kombinatorial isboti" (PDF), Amerika matematik oyligi, 63 (10): 718, doi:10.2307/2309563, JSTOR  2309563
  2. ^ Iga, Kevin (2003), "Fermaning kichik teoremasining dinamik tizimining isboti", Matematika jurnali, 76 (1): 48–51, doi:10.2307/3219132, JSTOR  3219132
  3. ^ a b v Dikson, Leonard Eugene (2005) [1919], "Ferma va Uilson teoremalari, umumlashmalari va suhbatlari; nosimmetrik funktsiyalari 1, 2, ..., p − 1 modul p", Raqamlar nazariyasi tarixi, Men, Dover, ISBN  978-0-486-44232-7, Zbl  1214.11001
  4. ^ Vakka, Jovanni (1894), "Intorno alla prima dimostrazione di un teorema di Fermat", Matematikaning bibliotekasi, 2-seriya (italyan tilida), 8 (2): 46–48
  5. ^ Alkauskas, Giedrius (2009), "Fermaning kichik teoremasining qiziq isboti", Amerika matematik oyligi, 116 (4): 362–364, arXiv:0801.0805, doi:10.4169 / 193009709x470236, JSTOR  40391097
  6. ^ Xardi, G. H.; Rayt, E. M. (2008), "Ferma teoremasi va uning oqibatlari", Raqamlar nazariyasiga kirish (6-nashr), Oksford universiteti matbuoti, ISBN  978-0-19-921986-5
  7. ^ Fil suyagi, Jeyms (1806), "tub sonlarga nisbatan teoremani namoyish etish", Matematik depozitariyning yangi seriyasi, 1 (II): 6-8
  8. ^ Lejeune Dirichlet, Piter Gustav (1828), "Démonstrations nouvelles de quelques théorèmes relatifs aux nombres", Journal für die reine und angewandte Mathematik (frantsuz tilida), 3: 390–393
  9. ^ Vayl, Andre; Rozenlixt, Maksvell (1979), "VIII §", Yangi boshlanuvchilar uchun raqamlar nazariyasi, Springer-Verlag, doi:10.1007/978-1-4612-9957-8, ISBN  978-0-387-90381-1, Zbl  0405.10001
  10. ^ Vayl, Andre (2007) [1984], "III.VI §", Raqamlar nazariyasi: tarixga yondashish; Hammurapidan Legendrgacha, Birxauzer, ISBN  978-0-8176-4565-6, Zbl  1149.01013
  11. ^ Eyler, Leonxard (1761), "Potestatum relicta bo'linmasidan oldingi teoremalar" (PDF), Novi Commentarii Academiae Scientiarum Petropolitanae (lotin tilida), 7: 49–82