Ферматтардың кішігірім теоремасының дәлелдері - Proofs of Fermats little theorem - Wikipedia

Бұл мақалада әртүрлі жинақталған дәлелдер туралы Ферманың кішкентай теоремасы, онда көрсетілген

әрқайсысы үшін жай сан б және әрқайсысы бүтін а (қараңыз модульдік арифметика ).

Жеңілдету

Кейбір Ферманың кішкентай теоремасының дәлелі төменде келтірілген екі жеңілдетуге байланысты.

Біріншісі - біз мұны ойлауымыз мүмкін а ауқымында 0 ≤ аб − 1. Бұл заңдардың қарапайым салдары модульдік арифметика; біз алдымен азайтуымыз мүмкін деп айтып отырмыз а модульб. Бұл төмендетуге сәйкес келеді модульб, біреу тексере алады.

Екіншіден, мұны дәлелдеу жеткілікті

үшін а диапазонда 1 ≤ аб − 1. Шынында да, егер алдыңғы тұжырым осындай болса а, екі жағын да көбейтіңіз а теореманың бастапқы формасын береді,

Екінші жағынан, егер а = 0, теорема маңызды емес.

Комбинаторлық дәлелдемелер

Алқаларды санау арқылы дәлелдеу

Бұл, мүмкін, ең қарапайым, ең аз математикалық негіздерді қажет ететін дәлелдеу. Бұл а-ның тартымды мысалы комбинаторлық дәлелдеу (қамтитын дәлел заттар жиынтығын екі түрлі тәсілмен санау ).

Мұнда келтірілген дәлел - бейімделу Голом дәлелі.[1]

Қарапайым болу үшін, осылай деп ойлайық а Бұл оң бүтін сан. Барлық мүмкіндікті қарастырыңыз жіптер туралы б белгілерін пайдаланып, алфавит бірге а әртүрлі белгілер. Мұндай жолдардың жалпы саны аб, өйткені бар а әрқайсысының мүмкіндіктері б позициялар (қараңыз. қараңыз) өнімнің ережесі ).

Мысалы, егер б = 5 және а = 2, содан кейін біз екі белгісі бар алфавитті қолдана аламыз (айталық A және B) және бар 25 = 32 ұзындығы 5:

ААААА, AAAAB, AAABA, AAABB, AABAA, AABAB, AABBA, AABBB,
АБАА, ABAAB, АБАБА, ABABB, АББАА, ABBAB, АБББА, АББББ,
БААА, BAAAB, БААБА, BAABB, БАБАА, БАБАБ, БАББА, BABBB,
ББАА, BBAAB, BBABA, BBABB, БББАА, BBBAB, BBBBA, BBBBB.

Төменде біз бір таңбадан тұратын жолдарды тізімнен алып тастасақ (біздің мысалда ААААА және BBBBB), қалғаны аба жолдарды топтарға бөлуге болады, олардың әрқайсысы дәл бар б жіптер. Бұдан шығатыны аба бөлінедіб.

Алқалар

Жеті түрлі ішекті білдіретін алқа (ABCBAAC, BCBAACA, CBAACAB, BAACABC, AACABCB, ACABCBA, CABCBAA)
Тек бір жіпті білдіретін алқа (ААААААА)

Әрбір осындай тізбекті а-ны бейнелейтін етіп қарастырайық алқа. Яғни, біз жіптің екі ұшын біріктіріп, мүмкін болса, екі жіпті бірдей алқа деп санаймыз айналдыру екінші жолды алу үшін бір жол; бұл жағдайда біз екі жол дегенді айтамыз достар. Біздің мысалда келесі жолдар дос болып табылады:

AAAAB, AAABA, AABAA, АБАА, БААА.

Сол сияқты, келесі тізімнің әр жолы жалғыз алқаға сәйкес келеді.

AAABB, AABBA, АББАА, ББАА, BAAAB,
AABAB, АБАБА, БАБАА, ABAAB, БААБА,
AABBB, АБББА, БББАА, BBAAB, BAABB,
ABABB, БАББА, ABBAB, BBABA, БАБАБ,
АББББ, BBBBA, BBBAB, BBABB, BABBB,
БААА, AAAAB, AAABA, AABAA, АБАА,
ААААА,
BBBBB.

Жоғарыда келтірілген тізімде бірнеше символдардан тұратын әр алқа 5 түрлі жолмен ұсынылғанына назар аударыңыз, ал бір ғана жіппен ұсынылған алқалар саны 2-ге тең, яғни нақты белгілер саны. Осылайша тізімде не үшін екені анық көрсетілген 32 − 2 бөлінеді 5.

Берілген жолды қанша досқа айналдыру үшін келесі ережені қолдануға болады S бар:

Егер S жолдың бірнеше көшірмесінен тұрғызылған Т, және Т оны одан әрі қайталанатын жолдарға бөлуге болмайды, содан кейін достарының саны S (оның ішінде S өзі) тең ұзындығы туралы Т.

Мысалы, біз жолдан бастайық делік S = ABBABBABBABB, ол қысқа жолдың бірнеше данасынан тұрғызылған Т = ABB. Егер біз оны бір-бірден айналдырсақ, келесі 3 жолды аламыз:

ABBABBABBABB,
BBABBABBABBA,
BABBABBABBAB.

Басқалары жоқ, өйткені ABB ұзындығы тура 3 таңбадан тұрады және оны қайталанатын жолдарға бөлуге болмайды.

Дәлелдеуді аяқтау

Жоғарыда аталған ережені қолдана отырып, біз Ферманың кішігірім теоремасының дәлелдеуін келесідей оңай аяқтай аламыз. Біздің бассейніміз а б жолдарды екі санатқа бөлуге болады:

  • Кейбір жолдарда бар б бірдей белгілер. Дәл бар а алфавиттегі әр таңба үшін біреуі. (Біздің жүгіретін мысалда бұл жолдар ААААА және BBBBB.)
  • Қалған жолдарда алфавиттен кем дегенде екі бөлек таңба қолданылады. Егер біз ажырасуымыз мүмкін болса S кейбір жолдардың қайталанатын көшірмелеріне Т, ұзындығы Т ұзындығын бөлу керек S. Бірақ, ұзындығынан бастап S премьер болып табылады б, үшін мүмкін болатын жалғыз ұзындық Т сонымен қатар б. Сондықтан жоғарыдағы ереже осыны айтады S дәл бар б достар (соның ішінде S өзі).

Екінші санатқа кіреді а ба жіптер, және олар топтарға орналасуы мүмкін б жіптер, әр алқа үшін бір топ. Сондықтан, а ба бөлінуі керек б, уәде етілгендей.

Динамикалық жүйелерді қолдана отырып дәлелдеу

Бұл дәлел кейбір негізгі ұғымдарды қолданады динамикалық жүйелер.[2]

Біз отбасын қарастырудан бастаймыз функциялары Тn(х), қайда n ≥ 2 - ан бүтін, картаға түсіру аралық [0, 1] формула бойынша өзіне

қайда {ж} дегенді білдіреді бөлшек бөлігі туралы ж. Мысалы, функция Т3(х) төменде көрсетілген:

Tn функциясының мысалы

Сан х0 деп аталады бекітілген нүкте функцияның f(х) егер f(х0) = х0; басқаша айтқанда, егер f жапырақтары х0 тұрақты. Функцияның бекітілген нүктелерін графикалық түрде оңай табуға болады: олар жай ғана х нүктелерінің координаттары график туралы f(х) түзудің графигімен қиылысады ж = х. Мысалы, функцияның бекітілген нүктелері Т3(х) 0, 1/2 және 1; олар келесі сызбада қара шеңберлермен белгіленеді:

Tn функциясының бекітілген нүктелері

Бізге келесі екі лемма қажет болады.

Лемма 1. Кез келген үшін n ≥ 2, функциясы Тn(х) дәл бар n бекітілген нүктелер.

Дәлел. Жоғарыда келтірілген суретте 3 тұрақты нүкте бар, геометриялық дәлелдеменің кез-келгеніне бірдей қолданылады n ≥ 2.

Лемма 2. Кез келген натурал сандар үшін n және мжәне кез келген 0 ≤ x ≤ 1,

Басқа сөздермен айтқанда, Тмн(х) болып табылады құрамы туралы Тn(х) және Тм(х).

Дәлел. Бұл лемманың дәлелі қиын емес, бірақ біз соңғы нүктеге аздап мұқият болуымыз керек х = 1. Осы сәтте лемма анық, өйткені

Сонымен, 0 ≤ деп есептейік х <1. Бұл жағдайда,

сондықтан Тм(Тn(х)) арқылы беріледі

Сондықтан, біз шынымен көрсетуіміз керек нәрсе - сол

Бұл үшін біз {nx} = nxк, қайда к болып табылады бүтін бөлігі туралы nx; содан кейін

бері mk бүтін сан.

Енді функцияны зерттеу арқылы Ферманың кішігірім теоремасын дәлелдеуге кірісейік Таб(х). Біз мұны болжаймыз а ≥ 2. Лемма 1-ден біз оның бар екенін білеміз аб бекітілген нүктелер. Лемма 2 арқылы біз мұны білеміз

сондықтан кез келген бекітілген нүкте Та(х) автоматты түрде белгіленген нүкте болып табылады Таб(х).

Бізді белгіленген нүктелер қызықтырады Таб(х) бұл емес нүктелерінің Та(х). Осындай нүктелер жиынтығын атайық S. Сонда аба нүктелер S, өйткені Лемма 1 арқылы тағы, Та(х) дәл бар а бекітілген нүктелер. Келесі диаграмма жағдайды бейнелейді а = 3 және б = 2. Қара шеңберлер - нүктелері S, оның ішінде 3 бар2 − 3 = 6.

S жиынындағы бекітілген нүктелер

Дәлелдеудің негізгі идеясы - қазір жиынтықты бөлу S оған дейін орбиталар астында Та. Бұл дегеніміз, біз нүктені таңдаймыз х0 жылы Sжәне бірнеше рет қолдануға болады Та(х) оған, нүктелер ретін алу үшін

Бұл реттілік орбита деп аталады х0 астында Та. Лемма 2 бойынша бұл тізбекті келесідей етіп жазуға болады

Біз мұны болжап отырғандықтан х0 нүктесінің бекітілген нүктесі болып табылады Та б(х), кейін б біз соққан қадамдар Таб(х0) = х0, және сол сәттен бастап реттілік қайталанады.

Алайда, реттілік мүмкін емес одан бұрын қайталануды бастаңыз. Егер ол орындалса, қайталанатын бөлімнің ұзындығының бөлгіші болуы керек еді б, сондықтан 1 болуы керек еді (бастап б қарапайым). Бірақ бұл біздің болжамымызға қайшы келеді х0 нүктесі емес Та.

Басқаша айтқанда, орбитада дәл бар б нақты нүктелер. Бұл кез келген орбитаға арналған S. Сондықтан жиынтық S, құрамында бар аб − а нүктелер, әрқайсысы бар орбитаға бөлінуі мүмкін б ұпай, сондықтан аб − а бөлінеді б.

(Бұл дәлелдеменің мәні бірдей алқаларды санауға арналған дәлел жоғарыда келтірілген, басқа линзалар арқылы қарастырылған: [0, 1] аралықты базадағы цифрлар тізбегі берілген деп санауға болады а (0 мен 1 арасындағы айырмашылық «.0000 ...» және «.9999 ...» аяқталатын бүтін сандарды ұсынудың арасындағы айырмашылыққа сәйкес келеді). Таn осындай реттілікті ауыстыруға тең болады n көптеген сандар. Мұның бекітілген нүктелері периодты бөлумен циклді болатын тізбектер болады n. Атап айтқанда, Таб ұзындықтағы алқалар деп санауға болады б, бірге Таn осындай алқалардың айналуына сәйкес келеді n дақтар.

Бұл дәлелдемені 0 мен 1-ді ажыратпай, жартылай ашық аралықты пайдаланып ұсынуға болады [0, 1); содан кейін Тn ғана болар еді n - 1 тіркелген ұпай, бірақ ТабТа әлі күнге дейін жұмыс істейтін еді аба, қажет болған жағдайда.)

Көпмүшелік дәлелдемелер

Биномдық теореманы қолдану арқылы дәлелдеу

Бұл дәлел Эйлер,[3] қолданады индукция барлық бүтін сандарға арналған теореманы дәлелдеу а ≥ 0.

Негізгі қадам, сол 0б ≡ 0 (модб), маңызды емес. Әрі қарай, егер теорема шындыққа сәйкес келсе, оны көрсетуіміз керек а = к, содан кейін бұл үшін де дұрыс а = к + 1. Бұл индуктивті қадам үшін келесі лемма қажет.

Лемма. Кез келген бүтін сандар үшін х және ж және кез-келген премьер үшін б, (х + ж)б ≡ хб + жб (модб).

Лемма - бұл жағдай бірінші курстың арманы. Дәлелді кейінірек қалдырып, индукцияға көшеміз.

Дәлел. Болжам кбк (мод б), және қарастыру (к+1)б. Лемма бойынша бізде бар

Индукциялық гипотезаны қолдана отырып, бізде бар кбк (мод б); және маңызды емес, 1б = 1. Сонымен

бұл теореманың тұжырымы а = к+1. ∎

Лемманы дәлелдеу үшін біз биномдық теорема, бұл кез-келген оң бүтін сан үшін n,

мұндағы коэффициенттер биномдық коэффициенттер,

тұрғысынан сипатталған факторлық функциясы, n! = 1×2×3×⋯×n.

Лемманың дәлелі. Көрсеткіш жай сан болғанда биномдық коэффициентті қарастырамыз б:

Биномдық коэффициенттер - бұл бүтін сандар. Нуматорда коэффициент бар б факториалды анықтамасы бойынша. 0 <болғанда мен < б, бөлгіштегі терминдердің екеуі де факторды қамтымайды б (-ның басымдылығына сүйене отырып б), коэффициенттің өзін жай көбейткішке ие етіп қалдыру б нумератордан, дегенді білдіреді

Модуло б, бұл биномдық теореманың оң жағындағы қосындысының бірінші және соңғы мүшелерінен басқаларының бәрін жояды б. ∎

Басымдылығы б лемма үшін маңызды; әйтпесе, бізде мысалдар бар

бұл 4-ке бөлінбейді.

Көпмоминалды кеңейтуді қолдану дәлелі

Алғаш ашқан дәлелі Лейбниц (кім жарияламаған)[4] кейінірек қайта ашылды Эйлер,[3] өте қарапайым қосымшасы болып табылады көпнұсқалық теорема мұнда қарапайымдылық үшін әкелінген.

Жиынтық теріс емес бүтін индекстердің барлық тізбектері бойынша алынады к1 арқылы км барлығының қосындысы кмен болып табылады n.

Осылайша, егер біз білдіретін болсақ а 1s (бірлік) қосындысы ретінде аламыз

Егер анық болса б жай және егер болса кj тең емес б кез келген үшін j, Бізде бар

және

егер кj тең б кейбіреулер үшін j.

Себебі дәл бар а элементтер кj = б, теорема шығады.

(Бұл дәлелдеменің дәлірек нұсқасы алқаларды санауға арналған дәлел бұрын берілген; көпмомиялық коэффициенттер жолды ерікті анаграммаға енгізу тәсілдерінің санын есептейді, ал алқа аргументі жолды циклдік анаграммаға айналдырудың санын есептейді. Мұндағы нитрийлік көпмомалды коэффициенттер бөлінеді деп айтуға болады б ұзындықтағы әрбір бейресми алқалардың болуының салдары ретінде қарастыруға болады б ішіне орауға болады б көптеген жолдар.

Бұл көп ұлтты кеңейту, әрине, оның негізінде жатыр биномдық теоремаға негізделген дәлелдеу жоғарыда)

Қуат өнімін кеңейтуді қолдану дәлелі

Гидриус ​​Алкаускас қуат көзін өнімнің ресми кеңеюіне негізделген аддитивті-комбинаторлық дәлел келтірді.[5] Бұл дәлелдеменің екеуі де қолданылмайды Евклидтік алгоритм не биномдық теорема, бірақ ол жұмыс істейді ресми қуат сериялары рационалды коэффициенттермен.

Эйлер теоремасының нақты жағдайы ретінде дәлелдеу

Бұл дәлел,[3][6] ашқан Джеймс Кот-д'Ивуар[7] және қайтадан ашылды Дирихлет[8] үшін біраз фон қажет модульдік арифметика.

Мұны ойлайық а оң және бөлінбейді б.Идея егер сандардың ретін жазып алсақ

 

 

 

 

(A)

және әрқайсысының модулін азайтыңыз б, алынған реттілік қайта құру болып шығады

 

 

 

 

(B)

Сондықтан, егер біз әр қатардағы сандарды көбейтсек, нәтижелер бірдей модуль болуы керек б:

Бірге жинау а терминдер кірістілік

Ақырында, біз нөмірлерден бас тартуымыз мүмкін 1, 2, ..., б − 1 алу, осы теңдеудің екі жағынан

Жоғарыда келтірілген дәлелдеудің екі кезеңі бар:

  • Неліктен тізбектің элементтері (A), қысқартылған модуль б, қайта құру болып табылады (B), және
  • Неліктен модульдік арифметика параметрінде «бас тарту» дұрыс болады.

Біз мұны төменде дәлелдейтін боламыз; алдымен осы дәлелдеудің мысалын іс жүзінде көрейік.

Мысал

Егер а = 3 және б = 7, онда қарастырылып отырған реттілік мынада

7 модулін азайту береді

бұл тек қайта құру

Оларды бірге көбейту береді

Бұл,

1 × 2 × 3 × 4 × 5 × 6 кірістілігін болдырмау

бұл Ферманың істегі кішігірім теоремасы а = 3 жәнеб = 7.

Жою туралы заң

Алдымен неліктен белгілі бір жағдайларда «бас тарту» жарамды екенін түсіндірейік. Нақты мәлімдеме келесідей. Егер сен, х, жәнеж бүтін сандар, және сен жай санға бөлінбейді бжәне егер

 

 

 

 

(C)

сонда біз «бас тартуға» болады сен алу

 

 

 

 

(Д.)

Біздің мұны пайдалануымыз күшін жою туралы заң Ферманың кішігірім теоремасының дәлелі жоғары болды, өйткені сандар 1, 2, ..., б − 1 әрине, бөлінбейді б (шынымен де олар кішірек қарағанда б).

Біз жою заңын оңай дәлелдей аламыз Евклид леммасы, егер ол қарапайым болса б өнімді бөледі аб (қайда а және б бүтін сандар), содан кейін б бөлу керек а немесе б. Шынында да, бекіту (C) жай мұны білдіреді б бөледі uxүй = сен(хж). Бастап б бөлінбейтін қарапайым сен, Евклидтің леммасы оның бөлінуі керектігін айтады х − ж орнына; Бұл, (Д.) ұстайды.

Жою туралы заңның талаптары өте қатал екенін ескеріңіз және бұл Ферманың кішкентай теоремасы неліктен мұны талап ететіндігін түсіндіреді б қарапайым. Мысалға, 2 × 2 ≡ 2 × 5 (мод 6), бірақ бұл дұрыс емес 2 ≡ 5 (мод 6). Алайда, күшін жою туралы заңның келесі жалпылауы қолданылады: егер сен, х, ж, және з бүтін сандар болып табылады, егер сен және з болып табылады салыстырмалы түрде қарапайым және егер

сонда біз «бас тартуға» болады сен алу

Бұл а Евклид леммасын жалпылау.

Қайта құру қасиеті

Соңында, біз неге дәйектілікті түсіндіруге тиіспіз

модулі азайған кезде б, реттіліктің қайта реттелуіне айналады

Бастау үшін, шарттардың ешқайсысы жоқ а, 2а, ..., (б − 1)а нөлдік модульге сәйкес келуі мүмкін б, егер болса к - сандардың бірі 1, 2, ..., б − 1, содан кейін к салыстырмалы түрде қарапайым б, және солай а, сондықтан Евклид леммасы бізге осыны айтады ка ешқандай фактормен бөліседі б. Сондықтан, кем дегенде, біз сандар екенін білеміз а, 2а, ..., (б − 1)а, модуль азайған кезде б, сандар арасында болуы керек 1, 2, 3, ..., б − 1.

Сонымен қатар, сандар а, 2а, ..., (б − 1)а барлығы болуы керек айқын оларды азайтқаннан кейін б, өйткені егер

қайда к және м бірі болып табылады 1, 2, ..., б − 1, содан кейін күшін жою туралы заң бізге осыны айтады

Екеуінен бастап к және м арасында 1 және б − 1, олар тең болуы керек. Сондықтан, шарттар а, 2а, ..., (б − 1)а модулі азайған кезде б анық болуы керек. Қорытындылау үшін: біз азайған кезде б − 1 сандар а, 2а, ..., (б − 1)а модуль б, біз дәйектіліктің нақты мүшелерін аламыз 12, ..., б − 1. Себебі дәл бар б − 1 осылардың ішіндегі жалғыздың мүмкіндігі - екіншісінің екіншісінің қайта құрылуы.

Эйлер теоремасына қосымшалар

Бұл әдісті дәлелдеу үшін де қолдануға болады Эйлер теоремасы, сандарының шамалы өзгерісімен 1 дейін б − 1 кем сандармен ауыстырылады және кейбір санмен копирленген м (міндетті түрде қарапайым емес). Қайта құру қасиеті де, күшін жою туралы заң да (аталған жалпыланған форма бойынша) жоғарыда ) әлі де қанағаттандырылған және оларды пайдалануға болады.

Мысалы, егер м = 10, онда сандар азм және м болып табылады 1, 3, 7, және 9. Осылайша бізде:

Сондықтан,

Эйлер критерийінің қорытындысы ретінде дәлелдеу

Топтық теорияны қолданатын дәлелдер

Стандартты дәлелдеу

Бұл дәлел[9] ең қарапайым элементтерін қажет етеді топтық теория.

Идея сол жиынтықты тану G = {1, 2, …, б − 1}, көбейту операциясымен (алынған модуль б) құрайды, а топ. Тек біршама күш жұмсауды қажет ететін топтық аксиома - бұл әрбір элемент G айналдыруға болады. Мұны бір сәтке сеніммен қабылдай отырып, солай деп ойлайық а ауқымында 1 ≤ аб − 1, Бұл, а элементі болып табылады G. Келіңіздер к болуы тапсырыс туралы а, Бұл, к болатын ең кіші оң бүтін сан ак ≡ 1 (модб). Содан кейін сандар 1, а, а2, ..., ак −1 қысқартылған модульб а кіші топ туралыG кімдікі тапсырыс болып табыладык сондықтан Лагранж теоремасы, к ретін бөледі G, қайсысы б − 1. Сонымен б − 1 = км оң сан үшін м содан соң

Әр элемент екенін дәлелдеу үшін б туралы G аударылатын, біз келесідей әрекет ете аламыз. Біріншіден, б болып табылады коприм дейін б. Осылайша Безуттың жеке басы бізді бүтін сандар бар екеніне сендіреді х және ж осындай bx + py = 1. Осы теңдік модулін оқу б, біз мұны көріп отырмыз х үшін кері болып табылады б, бері bx ≡ 1 (модб). Сондықтан, G айналдыруға болады. Сонымен, бұрын айтылғандай, G топ болып табылады.

Мысалы, қашан б = 11, әр элементтің кері шамалары келесідей берілген:

а12345678910
а −116439287510

Эйлердің дәлелі

Егер біз алдыңғы дәлелді алып, Лагранж теоремасын қолданудың орнына дәл осы жағдайда дәлелдеуге тырысатын болсақ, онда біз Эйлердің үшінші дәлелі шығады, ол оның табиғи деп тапқан дәлелі.[10][11] Келіңіздер A элементтері сандар болатын жиын бол 1, а, а2, ..., ак − 1 қысқартылған модульб. Егер A = G, содан кейін к = б − 1 сондықтан к бөледі б −1. Әйтпесе, кейбіреулері бар б1 ∈ G\A.

Келіңіздер A1 элементтері сандар болатын жиын бол б1, аб1, а2б1, …, ак − 1б1 қысқартылған модульб. Содан кейін A1 бар к нақты элементтер, өйткені басқаша екі нақты сандар болар еді м, n ∈ {0, 1, ..., к − 1} осылай амб1аnб1 (мод б), мүмкін емес, өйткені ол солай жүретін болады амаn (мод б). Екінші жағынан, A1 элементі бола алады A, өйткені әйтпесе сандар болар еді м, n ∈ {0, 1, …, к − 1} осылай амб1аn (мод б), содан соң б1аnакмаn + км (мод б), мүмкін емес, өйткені б1A.

Сонымен, жиынтық AA1 бар 2к элементтер. Егер ол тең болып шықсаG, содан кейін 2к = б −1 сондықтан к бөледі б −1. Әйтпесе, кейбіреулері бар б2 ∈ G\(AA1) және біз бәрін қайтадан бастауға болады A2 элементтері сандар болатын жиын ретінде б2, аб2, а2б2, ..., ак − 1б2 қысқартылған модульб. Бастап G ақырлы, бұл процесс бір сәтте тоқтауы керек және бұл оны дәлелдейді к бөледі б − 1.

Мысалы, егер а = 5 және б = 13, содан кейін, бері

  • 52 = 25 ≡ 12 (мод 13),
  • 53 = 125 ≡ 8 (мод 13),
  • 54 = 625 ≡ 1 (мод 13),

Бізде бар к = 4 және A = {1, 5, 8, 12}. Анық, A ≠ G = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}. Келіңіздер б1 элементі болу G\A; мысалы, алыңыз б1 = 2. Содан кейін, бері

  • 2×1 = 2,
  • 2×5 = 10,
  • 2 × 8 = 16 ≡ 3 (мод 13),
  • 2 × 12 = 24 ≡ 11 (мод 13),

Бізде бар A1 = {2, 3, 10, 11}. Анық, AA1G. Келіңіздер б2 элементі болу G\(AA1); мысалы, алыңыз б2 = 4. Содан кейін, бері

  • 4×1 = 4,
  • 4 × 5 = 20 ≡ 7 (мод 13),
  • 4 × 8 = 32 ≡ 6 (мод 13),
  • 4 × 12 = 48 ≡ 9 (мод 13),

Бізде бар A2 = {4, 6, 7, 9}. Ал қазір G = AA1A2.

Жинақтар екенін ескеріңіз A, A1және т.с.с. ғарыш туралы A жылы G.

Ескертулер

  1. ^ Голомб, Соломон В. (1956), «Ферманың» кішкентай «теоремасының комбинаторлық дәлелі» (PDF), Американдық математикалық айлық, 63 (10): 718, дои:10.2307/2309563, JSTOR  2309563
  2. ^ Ига, Кевин (2003), «Ферманың кішкентай теоремасының динамикалық жүйелерінің дәлелі», Математика журналы, 76 (1): 48–51, дои:10.2307/3219132, JSTOR  3219132
  3. ^ а б в Диксон, Леонард Евгений (2005) [1919], «Ферма мен Вилсонның теоремалары, жалпыламалары және сөйлесулері; симметриялы функциялары 1, 2, ..., б − 1 модуль б", Сандар теориясының тарихы, Мен, Довер, ISBN  978-0-486-44232-7, Zbl  1214.11001
  4. ^ Вакка, Джованни (1894), «Intorno alla prima dimostrazione di un teorema di Fermat», Bibliotheca Mathematica, 2 серия (итальян тілінде), 8 (2): 46–48
  5. ^ Алкаускас, Гедриус ​​(2009), «Ферманың кішкентай теоремасының қызықты дәлелі», Американдық математикалық айлық, 116 (4): 362–364, arXiv:0801.0805, дои:10.4169 / 193009709x470236, JSTOR  40391097
  6. ^ Харди, Г. Х.; Райт, Э. М. (2008), «Ферма теоремасы және оның салдары», Сандар теориясына кіріспе (6-шы басылым), Оксфорд университетінің баспасы, ISBN  978-0-19-921986-5
  7. ^ Піл сүйегі, Джеймс (1806), «жай сандарға қатысты теореманы көрсету», Математикалық депозитарийдің жаңа сериясы, 1 (II): 6-8
  8. ^ Леджен Дирихле, Питер Густав (1828), «Démonstrations nouvelles de quelques théorèmes relatifs aux nombres», Mathematik für die reine und angewandte журналы (француз тілінде), 3: 390–393
  9. ^ Вайл, Андре; Розенлихт, Максвелл (1979), «VIII §», Жаңадан бастаушыларға арналған теория, Шпрингер-Верлаг, дои:10.1007/978-1-4612-9957-8, ISBN  978-0-387-90381-1, Zbl  0405.10001
  10. ^ Вайл, Андре (2007) [1984], «§ III.VI», Сандар теориясы: Тарих арқылы көзқарас; Хаммурапиден Легандрға дейін, Бирхязер, ISBN  978-0-8176-4565-6, Zbl  1149.01013
  11. ^ Эйлер, Леонхард (1761), «The reemata circa residua ex divisione potestatum relicta» (PDF), Novi Commentarii Academiae Scientiarum Petropolitanae (латын тілінде), 7: 49–82