Twierdzenie Eulera z dowodem przez lemat LTE — kółko IMPAN
Kółko matematyczne IMPAN⏱ 45 min
Follow-up po spotkaniu kółka matematycznego IMPAN z 18.03.2026: zapowiedź kolejnych zajęć z teorii liczb i omówienie zadań, które zostały z poprzedniego tygodnia. Pojawia się twierdzenie Eulera z dowodem opartym na lemacie LTE.
W tym nagraniu
Funkcja Eulera φ(n) i twierdzenie Eulera, małe twierdzenie Fermata
Dowód twierdzenia Eulera z lematu LTE
Wielomiany o wartościach całkowitych i część całkowita (podłoga)
Podzielność sum ciągów geometrycznych przez liczbę pierwszą
Nagranie uzupełnia spotkanie kółka matematycznego IMPAN z 18 marca 2026 roku: zapowiada zajęcia z 25 marca, z podpowiedziami do zadań, i omawia zadania, które zostały z poprzedniego tygodnia — m.in. wielomiany o wartościach całkowitych, część całkowitą (podłogę) i podzielność sum ciągów geometrycznych przez liczbę pierwszą.
Główny wątek to teoria liczb: funkcja Eulera φ(n), czyli liczba liczb ze zbioru {1, …, n} względnie pierwszych z n, i twierdzenie Eulera — jeśli NWD(a, n) = 1, to a^φ(n) ≡ 1 (mod n). Szczególnym przypadkiem dla n = p pierwszego jest małe twierdzenie Fermata: a^(p−1) ≡ 1 (mod p).
Dowód twierdzenia Eulera jest poprowadzony nietypowo — przez lemat LTE (lifting the exponent), który mówi, jaka potęga liczby pierwszej p dzieli różnicę potęg aⁿ − bⁿ. Po drodze pojawia się też lemat o podzielności symboli Newtona, przydatny jako podpowiedź do zadania 2.9.
Rozdziały
Kliknij czas, żeby przewinąć nagranie do wybranego fragmentu.
Zapowiedź spotkania 25.03.2026, w tym hinty do zadań
Zadanie 1.1
Zadanie 1.6
Lemat o podzielności symboli Newtona, hint do 2.9
MTF
LTE
Twierdzenie Eulera
Opis i materiały
Instytut Matematyczny PAN zaprasza pasjonatów w środy w godzinach 16-18 do sali 321 na makrodawkowanie matematyki.
Transkrypt został wygenerowany automatycznie na podstawie napisów YouTube, więc może zawierać błędy w zapisie wzorów, nazwisk i terminów. Kliknij znacznik czasu, aby przewinąć wideo do danego fragmentu. (4289 słów)
Dziękuję bardzo publiczności za przybycie w zeszłą środę i tradycyjnie chciałbym zareklamować najbliższe kółko i zrobić remanent z poprzedniego. Za dwa dni będziemy dalej męczyć teorię liczb. Zadania, które tutaj widzicie i które są w PDFie, a w linku pod filmem są w większości do zrobienia na chłopski roz, tak po prostu z własności kongruencji. Jest jeden nowy bohater, to znaczy twierdzenie Oilera.
Ten ten śmieszny znaczek to jest to jest liczba liczb w zakresie od 1 do n, które są względnie pierwsze z n. To jest najleniwsze, czyli najlepsze oznaczenie na to, że NWDKn jest równe 1. I twierdzenie mówi tyle, że że jeśli a jest względzie pierwsze z n, to a do funkcji Oilera przestaje do jeden modulu n. Gołym okiem widać, że założenie jest konieczne, bo gdyby a i n miały wspólny wspólny dzielnik, to wtedy jeden też musiałby się przez niego dzielić i byłaby klapa.
Wyjście z tego twierdzenia jako szczególny przypadek wynika małe twierdzenie fermata dla n będącego liczbą pierwszą. Normalnie bym zostawił to twierdzenie jako kursowy fakt, którego dowód jest wszędzie, ale jako, że zajmowaliśmy się tematem LTE, to pokażę dowód, który który wynika właśnie z tego lematu. Co jeszcze chcemy wiedzieć? Chcemy wiedzieć, że zadanie jest wnioskiem z czy wnioskiem jest mutacją jest mutacją zadanie 1.6 z poprzedniej serii, które które jeszcze obejrzymy.
Zadanie 214 to my to zrobiliśmy ostatnio dla Qego 2. No i polecam najpierw się zastanowić jak to wygląda dla Q naturalnych, czy daje się przenieść to rozumowanie, które zrobiliśmy i potem zobaczyć, co się zmienia dla Qwymiernych. Zabawne, że jak sam się przyglądałem temu 214, to bałem się, że żeby się z niego wytłumaczyć, będzie trzeba robić rozszerzenia ciał, ale ale na szczęście nie. To się daje robić w normalnej arytmetyce module liczba pierwsza.
Generalnie zadanie 213 nie wynika bezpośrednio z 1.6, tylko po prostu używa się idei, która jest mutacją tego, co jest w 1.6. No jeśli chodzi o zadanie 2015 to ono jest przepiękne i firmówka jest przepiękna, natomiast wpadnięcie na nią jest cóż, to ja chciałem zaproponować hint w inną stronę, żeby się zastanowić nad czymś takim. Ja mam wielomian. o wspócznikach wymiernych i ja mam na nim operator delta, który z wielomianu f robi taki nowy wielomian, że on w punkcie t zwraca f t + 1 - f t.
I ja polecam się zastanowić nad tym. To nie jest tajemnica, że to też jest wielomian. I stopnia koniecznie stopień f-1. No chyba, chyba, że F był, chyba że F był stały. Ja polecam się zastanowić nad tym, jak wygląda zależność między klejem dla każdego na całkowitego. F n jest całkowite z kleimem f od zer jest całkowite oraz dla każdego na całkowitego delta f od n jest całkowita.
To wygląda jak głupi warunek, no bo wygląda jakby to chodziło wielomianę współcznikach całkowitych. A tu nie, tu nawet treść zadania podpowiada wielomiany, które pokazują, że w tym warunku coś chodzi. Tak na przykład wielomian f równy taka potęga krocząca przez nen silnia. On nie ma całkowitych współczynników, ale po polsku się nazywa TN. I jak zastosuję tu całkowite t, to wyjdzie liczba całkowita. Więc to jest taka inspiracja do tego, jak można wymyślić rozwiązanie, na które da się wpaść.
To żebyśmy zrobili porządek z tym co zostało. Zaczął od 1.6, bo ono jest najprostsze, nie? Najprostsze w ogóle jest 11 z zadań, które chcę zobaczyć zrobione. Tak, ale 11 to jest to jest taka rozgrzewka. To jest tak, że łatwo się przekonać, że x kw przystaje do modulo 3, do 0 lub 1. Tak? No bo sprawdzamy po prostu na ha po kolei. Jak tu jest x i tu jest x kw modulo 3, to tu jest pełna lista reszty zdzielenia przez 3 i tu jest pełna lista reszt kwadratów.
Analogicznie sprawdzamy, że x kw też przestaje do zera albo do jedynki. Czyli jak nam każą udowodnić, że 12 dzieli xy, to nam każe udowodnić dwie rzeczy. Pierwsza jest taka, że 3 dzieli xy, czyli że 3 dzieli x lub 3 dzieli y, a druga jest taka, że 4 dzieli x lub 4 dzieli y. No to gdzie się dowodzi tak samo. Przypuśćmy, że nie. Jeśli nie, jeśli 3 nie dzieli x, to x kwadrat musi przestawiać do jedynki modulo 3, bo nie może do zera, bo jakby przestawał do zera, to x byłby podzielny przez 3, a nie jest. Tak. No i tak samo y² przestaje modl 3 do 1, więc z kw zadania przestaje modelu 3 do 2. No i to jest sprzeczność.
No i tu tak samo. No to już udowodniliśmy. Zaprzeczenie tego, co prowadziło do sprzeczności. Zaprzeczenie tego identycznymi napisami prowadzi do sprzeczności. W związku z tym trójka dzieli któregoś z nich, czwórka dzieli któregoś z nich, 3 dzieli xy, 4 dzieli xy, 3 jest względnie pierwsze z 4, więc więc 12 dzieli xy. To była taka rozgrzewka, żeby się żeby sobie przypomnieć, że kwadraty liczb całkowitych dają nieprzypadkowe reszty zdzielenia. Dobra, zadanie 14. A ono może zostać.
Zadanie 1.6. 14 jest zabawnym. Zrobiliśmy kawałek. Druga część jest yyy jest robialne. No yyy w sedaniu 1.6 jest taki enigmatyczny warunek. No i generalnie o takich o takich napisach się myśli w taki sposób, że skoro i tak myślimy o wielokrotnościach tych liczb, to tak na chłopski rozum 1 przez a1 to jest takie prawdopodobieństwo, że jak zalosuję liczbę naturalną, to trafię w wielokrotność A1.
Oczywiście to jest stwierdzenie natury heurystycznej, bo z losowaniem jednostaj liczby naturalnej są same problemy, ale tak w przybliżeniu jak losujemy liczbę naturalną od 1 do miliona i A1 jest niewielkie to w przybliżeniu jest prawne. W tym zadaniu akurat to trzeba policzyć dokładnie, ale tu po prostu skonujemy rozwiązanie od Neiga Bauera, bo bo ono jest tym jedynym, który się narzuca. I rozwiązanie jest takie, że mówimy, że AK to są wielokrotności liczby AK w przedziale w tym, w którym się dzieje impreza, czyli od 1 do 1951.
I ten warunek, który jest tu napisany, że najmniejsza wspólna wielokrotność dowolnych dwóch jest większa niż niż niż nasz zakres. To efektywnie nam mówi tyle, że w tym zakresie nie spotkamy żadnej liczby, która jest jednocześnie wielokrotnością ai i aj dla i różnych od j. Czyli to, że NWW A i AJ jest większe niż 1951 dla różnego od J. To tak naprawdę efektywnie jest równoważne z tym, że a jest rozłączne z AJ. No i tu się już jawi rozwiązanie.
Mamy rozłączne zbiory. Ich gęstości są z grubsze takie jak rzeczy, które sumujemy i nas pytają o ograniczenie tych gęstości. To musi coś chodzić o dodawanie miar, więc my po prostu brutalnie liczymy, ile elementów ma suma tych wszystkich zbiorów. Ich jest niżej nieokreślone n. One są rozłączne, więc liczba ich elementów to jest to jest suma ich liczb elementów. No i teraz teraz się trzeba temu dokładnie przyjrzeć, ile jest wielokrotności jakieś liczby w takim przedziale. Pierwsza, którą spotkamy to jest a1, druga to jest 2a1.
Tak? Czyli jak się zastanawiamy ile to jest liczność AK, to jest dokładnie liczba tych jów większych równych 1, takich, że j wielokrotność ak mieści się w naszym zakresie, ale zaraz tu jest napisane, Jsze równe niż pewna konkretna liczba. No to to jest po prostu odliczanie liczb całkowitych do poniżej jakiejś liczby rzeczywistej. To z definicji jest część całkowita.
Po polsku podłoga, tak? Czyli naj największe oszacowanie z dołu liczbą całkowitą. To świetnie. To stosujemy ten wzór dla dla każdego k od 1 do n. No i dostajemy sumę podług. Tak, to jest prawie to, co tam mamy. Tylko, że są podłogi. Tam chcemy mieć coś liniowego od jeden przez. Czasem w takich napisach się opłaca zrobić szacowanie przez czynnik. Tu akurat opłaca się powiedzieć, że szacujemy to brutalnie z dołu z ostrą nierównością przez te liczby, które zaokrągamy w dół -1. Ta nierówność zawsze jest ostra.
Tak, to jest ogólne prawo natury, że jak mam liczbę rzeczywistą, tu mam gdzieś jej podłogę, tu mam gdzieś jej podłogę plus 1, to x - 1 musi być ostro mniejsze od podłogi, bo gdyby x - 1 było większe lub równe podłodze to x + 1 to podłogą x + 1 byłoby to podłogą xa byłaby podłoga x + 1. No. No i to jest prawie to co chcemy.
No bo tu mamy zbiory rozłączne, które siedzą w takim w takim obiętnym zbiorze, więc one mają razem co najwyżej tyle elementów, więc liczba była totalnie arbitralna. No i tu mamy napisane to, co chcemy, żeby się skróciło razy suma, ale jeszcze minus tyle jedynek, ile było tych liczb. No to z tego możemy po prostu napisać, że ta suma odwrotności, o którą nas pytają, jest jaka? Jest mniejsza niż 1951 + n1.
Ale n to była liczba naszych liczb. Tak. W treści zadania było napisane, że one są rosnące, więc ich jest co najwyżej tyle, co liczb w tym zakresie i weszło. To było takie zadanie worek treningowy. Ostatnio dowodziliśmy tematu LTE, ale ja chciałbym pokazać trochę bardziej wyczyszczony dowód, bo to jest tak, że ten trudniejszy krok my zrobiliśmy, my zrobiliśmy jednym przejściem za dużo.
Dało się, dało się zrobić krócej. No i 110 możemy zostawić. 19 możemy zostawić, bo to jest dobra rozrywka. To też jest dobra rozrywka. Więc tak, więc chcemy się przekonać o macie LTE i o tym, jak z niego wynika twierdzenie Oilera. To jeszcze zrobię. Czy ja zrobię prelemat? Tak, generalnie wypadałoby, bo my niby znamy małe twierdzenie formata, ale chciałem, żebyśmy zobaczyli pewien szczególny mechanizm dowodowy, który za nim stoi, bo jeden jest taki.
P domyście jest liczbą pierwszą. Chyba, że zapomnę powiedzieć, że nie jest i k jest od 1 do p-1, to jest ważne. To wtedy p dzieli symbol Newtona. Dowodów można robić tonę. Mój ulubiony, który przy okazji jest hintem do zadania, któreż to było? Do zadania 29. A mój ulubiony dowód jest taki, y, bo ja chcę policzyć ile jest podzbiorów k elementowych w zbiorze p elementowym, tak? Bo to z definicji jest ten, ten napis.
No to ja mogę zrobić yyy ja mogę zrobić taką funkcję. Ja mogę zrobić funkcję translacja, która działa na k elementowe podzbiory zbioru od 1 do p albo dla ustalenia uwagi od 0 do p- 1. bardzo prosty sposób t od zbioru to jest po prostu zbiór plus 1. Wiadomo, to to pracuje modul. Więc jak licznik się przebije do do P, to wraca do zera.
No i nie trudno się przekonać, że ten cały świat elementowych podzbiorów się rozpada na orbity w tym przekształceniu. To jest tak, że jak mam jakiś zbiór, to ja sobie zadziałam tym przekształceniem T, dostanę T od A, potem zadziałaniem jeszcze raz dostanę t kwat a i będę tak sobie działał. No i to jest proste ćwiczenie, które polecam sobie przemyśleć, że ja się zapętlę nie wcześniej.
Znaczy jeśli nie trafiłem głupiego zbioru, to znaczy pustego albo całości, co jest wykluczone przez fakt, że liczba elementów tych zbiorów jest nie zero i nie p, to ja się zapętl nie wcześniej niż po niż po pkrokach. I to znaczy w zasadzie tyle. To znaczy cały świat elementowych podzbiorów, zbioru elementowego rozpada się na takie orbity. Bardzo łatwo się przekonać, że one są rozłączne, bo gdyby taka orbita się przecinała z jakąkolwiek inną, która sobie idzie swoim przekształceniem T, to by znaczyło, że ta orbita kiedyś też dojdzie do sporatem do zbioru A.
Więc takie orbity jak się przecinają to muszą mieć to samo. Jakbym chciał używać feny terminologii, to bym powiedział, że że rozbijam ten zbiór tych kalementowych podzbiorów na klasy na klasy abstrakcji. Ale chłopski rozum po prostu mówi tyle, że bierzemy nasz ulubiony zbiór, drepczemy po po orbicie, zliczamy, że jest, że jest pz zbiorów, a odsuwamy ten zbiór na bok i jak zaczniemy od naszego nowego ulubionego zbioru, to będziemy dreptać po jakiejś tam rozłącznej orbicie, bo gdyby nie była rozłączna z tamtą, to byłaby tą samą.
Dalszym wnioskiem z tego jest małe twierdzenie fermata. Tak. No bo zobaczcie, małe twierdzenie fermata tak naprawdę mówi tyle, że taka funkcja modulo P to jest nasza ulubiona funkcja liniowa. No i jak to się sprawdza? To się sprawdza tak, że się patrzy na operator różnicy skończonej, tak? To znaczy wystarczy też także robimy indukcję wystarczy, że 0 do pstaje do zera oraz że a + 1 do p te - a do pstaje do a + 1 do p tej właśnie nie do p tej min a tak no to jest no brainer to jest także jak dodamy ten kleim do założenia indukcyjnego, to dostaniemy krok indukcyjny.
No to to jest równoważne z napisem a + 1 do p te - a do p tej -1 ma przstawać do zera. Ale to się rozpisuje z dumian Newton. To jest suma p. A priori ona jest od k rówego 0 do p z a do k tej, ale jeszcze tej sumie urywamy a do p tej i urywamy 1. Ale to jest składnik dla k rówego p, a to jest składnik dla k rów 0. Więc ta suma to jest po prostu suma od k rówego 1 do p z p po k a do k tej do p min 1 i o tym p po po k w tym zakresie k bez tych skrajnych które są równe 1 to się przed chwilą przekonaliśmy, że to jest podzielne przez p. Więc jak to przstaje do do zera modulo p całość przestaje do zera modulo p.
Zabawne, że twierdzenie się tak nie udowodni. Jak się przywali operator rzucicy skończonej do funkcji a do potęgi <un od n + 1, to wcale nie wychodzi wielomian, którego współczynniki są podzielne przez przez n. No i jakoś sobie z tym poradzimy. Dobra, jak mamy to, to możemy zrobić taki zoptymalizowany dowód lematu LTE. To znaczy po prostu dowód LTE, bo chociaż nie, L jest od lifting, tak? To jest lifting the exponent l.
I założenia były takie, że liczba pierwsza nie dzieli xa i y, ale dzieli ich różnicę. Bez tych założeń to to w ogóle idea dowodu nie działa. Ale tu jest jeszcze drobnym druczkiem, że dla p rówego 2 dodatkowo wymagamy, żeby to jednak p kwadrat ciło x- y. No i teraz chcemy się dowiedzieć z jaką potęgą p dzieli x do k - y do kte. Nie jest dla nas tajemnicą, że przynajmniej jest taką jak x- y. Natomiast ten mówi, że nie dość, że jest przynajmniej taką, to jeszcze dokładnie taką.
Dla dla przypomnienia to jest tak zwany wykładnik peyczny. Tak, czyli to jest największy największa taka liczba, że p do potęgi od dzieli dzieli z. No i aż się prosi, żeby zrobić redukcję o redukcję tego wykładnika, tak żeby się pozbyć czynników, które są niepodzielne przez p, bo te z elementematu twierdzi, że one nie kontrybuują do tego, ile p znajdziemy tutaj. Więc to będzie pierwszy krok.
Pierwszy klej jest taki, że jeśli p nie dzieli k, to wykładnik peadyczny x do k- y do k jest dokładnie równy wykładnikowi peadycznemu x- y. No i tego dowodzimy dokładnie tak jak na poprzednim kuku. To tylko napiszemy dla przypomnienia, bo napiszemy x do k min y do k jak tak jak w szkole. x- y razy ten wzór, który wygląda jak dwum newtona tylko, że bez współczynników, a tak naprawdę jest wzorem na sumę wyrazów ciągu geometrycznego. I co się tutaj dzieje?
No chcą od nas czegoś takiego, czyli tak naprawdę chcą, żebyśmy udowogodnili, że to nie kontrybuje do podzielności przez p. Czyli po prostu, że nie jest podzielne przez p. Czyli wystarczy dobadać moduło do P. Ale przypomnijmy sobie, że P, czyli X- Y, to ten składnik od tego się różni. Podzielenie przez x i pomnożenie przez y. Tak, żeby nikt nie narzekał na to, że dzielę przez x, to x jest niepodzielne przez p. Tak? No i to tak idzie indukcją, tak? x do i + 1y do j przystaje modula p do x do i y do j + 1.
Więc to wszystko, to całe towarzystwo, to przystaje model p do x- pj. Mamy tu dokładnie k sztuk. Są numerowane od 0 do k- 1. No i teraz x był niepodzielny przez p. K też zakład zakładaliśmy, że jest niepodzielne przez P. Czyli to jest niepodzielne przez P. Czyli całe występowanie P w tym pochodzi stąd. Czyli udowodniliśmy ten klej.
Dobra. Czyli tak naprawdę to nam zredukowało zadanie do takiego, w którym ten k tutaj jest potęgą P. Tak. No bo teraz jeśli nasz k jest równy powiedzmy py p do a x b to wtedy wykładnik peadyczny x do k - y do k to jest wykładnik padyczny x do p do a x b - y do p do a x b. Teraz to chcemy napisać jako bet potęgi. Oczywiście tu nie napisałem, że że p już nie dzieli b, czyli efektywnie a jest wykładnikiem pariadycznym K.
Tu jest X do P do A, tu jest do potęgi B - Y do P do A do potęgi B. No i tu jeszcze musimy zweryfikować, że żeby zastosować ten claim 1, to te podstawy muszą spełniać założenia, ale tu nam wolno, bo co? No bo x był niepodzielny przez p do jakiejś potęgi też jest niepodzielny przez p. A jak x przystaje do y modelu p, to oczywiście z tego wynika, że X do Pstaje do Y, do P. Mod P.
No i tak dalej. X do P do A przystaje do Y do P do A. Czyli są spełnione te dwa założenia tej tej wersji lematu LTF, której wykładnik nie dzieli się przez P. Czyli to jest dokładnie to od X do p do a - y do P do A. Tak. No i my chcemy udowodnić, że to jest wykładnik peadyczny x - y + a. Tak, te równości są zagwarantowane, czyli pytamy się o o równość tych dwóch rzeczy, bo to ta to ta równość nas sama naprowadza na to, co mamy zrobić.
Spodziewamy się, że to pochodzi od faktu, że wykładnik padyczny x do p do a - y do p do a jest równy wykładnik padyczny x do p do a - 1 - y do p do a - 1 + 1. No i potem indukcja. tak długo jak a jest większe równe 1. Tak, bo zatrzymujemy się wtedy na a równym 0. Tu jest x do p y do pierwzej. Dostajemy to yy to możemy jeszcze to wyczyścić mówiąc, że niech duże x to będzie małe x do p do a - 1. Duże y to będzie małe y do p do a - 1. wtedy w dalszym ciągu z tych samych powodów, które były tutaj, a duże X i duże Y spełniają założenia.
Czyli, czyli my chcemy udowodnić, że wykładnikyczny x do p- y do p jest równy wykładnikowi poadycznemu x- y + 1. I teraz ten dowód, który wcześniej robiliśmy był taki, że my najpierw to rozkładaliśmy jako x- y razy suma pewnych ilidoczynów i potem te iloczyny traktowaliśmy dwmiany Newtona. A nie trzeba tego robić. Wystarczy powiedzieć, że niech y to będzie x plus coś. To coś musi być podzielne przez p.
Niech będzie p raz jakiś z. Oczywiście tutaj minus nie ma znaczenia, więc jak ja chcę napisać y do p- x do p tej to jest x + pz do p tej min x do p tej i to jest ten sam motyw co w tym klasycznym dowodzie, który przed chwilą widzieliśmy. Tutaj robi się wielki dumion Newtona, w którym się aż roje od podzielności przez p. Tu jest suma od zera do p z p raz x do potęgi p- j p do potęgi j z do j- x do p. No i to x do p to jest składnik dla j równego dla j rów 0.
Więc jak urwiemy z tej sumy składnik do j rów 0, to dostajemy sumę od j rów 1 do p. Pamiętajmy o co walczymy. Chcemy się przekonać, że zostanie nam wykładnik peyczny x- y + 1. X- y to jest p z. Czyli chcemy dostać tut wykładnik paradyczny z, który może być zero plus 2. No ale to widać jak na dłoni, bo tu my zaczynamy sumę od równego 1, czyli p do p-ze x p x z wygląda jakby się zgadzało.
Potem wszystko co jest dalej to ma tu podzielność przez P i tu ma jeszcze więcej P. Jak tu ma P2, które jest podzielna przez P razy jakaś potęga X, która jest niepodzielna przez P razy P do kwadratu z do kwadratu i tak dalej. To jak my walczymy o to, żeby udowodnić, że tu jest dokładnie tyle p co w Zie, jeszcze plus 2, no to my po prostu wyciągamy p kwat z przed nawias. Tu już mamy 2 plus vp z w of potęgi p i zostajemy z x do p- pzej, które jest niepodzielne przez p plus cała taka suma.
Plus p 2 x do p- dr p właśnie nie raz p raz z kw plus p po 3x do p- tr z sścian i tak dalej i teraz wystarczyłoby nam powiedzieć że skoro to jest podzielne przez To nie jest to ta całość nie jest podzielna przez p i jesteśmy zrobieni normalnie. To by po prostu wynikało z naszego lematu o tym, jak się zachowuje podzielność przez p symboli dwumianowych.
Złośliwie jeszcze powiedzą, że na końcu się kończy ten kończą się symbole dwumionowe, ale ja tu jeszcze zgubiłem coś. Tak, ja tu zgubiłem to, że w następnym składniku mielibyśmy jeszcze jeszcze jedno p. Tak, bo tu urosną potęgi p z hmm yyy nie tak tam było następne było p z wyciąg p kw i to jest prawie koniec prawie koniec z dokładnością do tego, że przypadek równa się 2. Dla p rów 2 p nie dzieli p po 2. W tym jednym miejscu jest zongk.
Ale z pomocą w naszym klejmie, że to wszystko się dzieli przez p, przechodzi to, że zakładaliśmy, że zakładaliśmy, że z ma dodatkowe p, tak? Ale zakładaliśmy, że p², czyli 2² dzieli p x z yyy czyli p dzieli z. Czyli już tutaj z tego powodu mamy podzielność przez p. A dalej oczywiście idzie z a symbol wymianowych i z tego rosnącego p tutaj. I już koniec. udowodniliśmy o o jedno rozpisywanie na sumę mniej niż niż oryginalnie i to ja bym chciał jeszcze zakończyć na wywnioskowaniu z tego twierdzenia eilera y wniosek Wniosek to jest to, że a do <un n przystaje do 1 modu n.
Tu się posłużymy kursowym faktem, że jeśli n ma rozkład na czynniki pierwsze, to wtedy i to są faktycznie czynniki, to znaczy one są przynajmniej jeden, to wtedy fen się wyraża wzorem, że to jest iloczyn. PJ- 1 x PJ do alfa j- 1 i to jest całkowicie kursowy fakt. Jego się dowodzi w dwóch w dwóch kawałkach. To znaczy jego się dowodzi najpierw przez multiplikatywność.
I przez to jak to działa na potęgach liczb pierwszych, to generalnie jest łatwe. A tu no chcemy udowodnić, że coś się dzieli przez n. No to wystarczy wystarczy, żeby się dzieliło przez każdy z względnie pierwszych czynników na. Czyli wystarczy, żeby p do alfa dzieliło a do fi - 1. Niech będzie pj do alfa j dla każdego j.
Ale zaraz pi ten jest iloczynem, więc jak ja udowodnię, że a po prostu do potęgi <un od tego czegoś, tak? czyli do potęgi PJ - 1 x PJ do potęgi alfa j- 1, żeby przystawało do jedynki modulo PJ do alfa j. Jak już przestaje do jedynki, to jak to podniosę do jakiejkolwiek dalszej podęgi, tutaj będzie przestawał do jedynki. Teraz już żeby a albo dobra nawet już nie musimy czyścić oznaczeń.
No bo o co o co teraz chodzi ze stosowaniem elementatu LTE? Tu mamy naturalną sytuację. A do potęgi liczba pierwsza min jynka to jest matchm inaven. A do potęgi nasza liczba pierwsza min 1 i jedynka spełniają założenie lematu. Już wyczyśćmy wyczyśćmy oznaczenia tak, żeby się nie plątało j. Tu jest, tu jest p- 1 na poziomie p. Tu jest też min1 na poziomie wykładnika i tu jest p do alfa.
No i nasz input dylematu LTE to jest a do potęgi P - 1, a Y to jest 1. Tak? One oczywiście się nie dzielą przez P, ponieważ A było względnie pierwsze z nem, czego nie napisałem tutaj, napisałem wcześniej. W szczególności one są one są niepodzielne przez p, a p dzieli x- y z małego twierdzenia fermata, bo p dzieli a do p- a, czyli a x a do p- 1- 1, a p nie dzieli W związku z powyższym wykładnik padyczny a do p- 1 x p do potęgi alfa- 1- 1 do potęgi p do alfa- 1 równy wykładnikowi poadycznemu a do p- 1- 1 plus alfa-
Tu jest równość, ale my zbrutalizujemy t równość. Powimy, że jest większe równe. To się dzieli przez p, więc to jest większe równe 1. 1 + alfa - 1, czyli alfa. Czyli udowodniliśmy, tak po prostu udowodniliśmy, że to się dzieli przez P2 alfa. Uważny słuchacz zauważyłby, że tu jeszcze zrobiliśmy oszustwo, bo dla równego 2 to nie działa tak dobrze. Na szczęście dla prego 2 jest osobna sztuczka. Dla prównego 2 nie mamy zagwarantowanego tego założenia lamatu LTE, ale dla Pów 2 to jest w ogóle inna inna zabawa.
A jest wtedy nieparzyste, czyli ja muszę udowodnić, że a do potęgi 2- 1, czyli 1 x 2 do alfa - 1 przestaje do jedynki modlu 2 do alfa, czyli ja muszę w a do 2 do alfa - 1 znaleźć alfa czynników parzystych. No to jedziemy z różnicy kwadratów. Jedziemy, rozwijamy. Tu naliczyłem alfa -1 sztuk i tu jeszcze jedno, czyli tu jest alfa czynników, czyli to się dzieli przez 2 do alfa. No i tyle. No to yyy to pozostaje mi jednym życzyć powodzenia na finale Oma.