Kongruencje — reszty z dzielenia, małe twierdzenie Fermata i zadania
Arytmetyka modularna od zera: reszta z dzielenia potęgi, ostatnia cyfra, małe twierdzenie Fermata, Euler, chińskie twierdzenie o resztach i 12 przykładów.
Kongruencje to język, w którym teoria liczb mówi o resztach z dzielenia: zamiast pisać „liczby 38 i 3 dają tę samą resztę przy dzieleniu przez 7”, piszemy krótko \(38 \equiv 3 \pmod{7}\) i dalej liczymy prawie jak w zwykłej algebrze. Po tej lekcji będziesz sprawnie wyznaczać resztę z dzielenia potęgi i ostatnią cyfrę potęgi, stosować małe twierdzenie Fermata i twierdzenie Eulera, rozwiązywać kongruencje liniowe i małe układy z chińskiego twierdzenia o resztach, a także dowodzić, że równanie nie ma rozwiązań w liczbach całkowitych, patrząc na reszty kwadratów i sześcianów. Arytmetyka modularna to podstawowe narzędzie na Olimpiadzie Matematycznej i w konkursach, a na maturze rozszerzonej skraca zadania o resztach i dowody podzielności — zapis kongruencjami jest tam w pełni akceptowany, o ile każdy krok jest uzasadniony. Zakładamy, że znasz dzielenie z resztą oraz cechy podzielności, liczby pierwsze i NWD. Dwanaście przykładów prowadzi od rachunków na resztach (PP, PR — poziom matury) do poziomu olimpijskiego (OM). Najprostsze użycie reszt w szkolnych zadaniach to szukanie największej liczby pięciocyfrowej podzielnej przez daną liczbę.
Co to jest kongruencja — definicja i intuicja zegara
Na przykład \(38 \equiv 3 \pmod{7}\), bo \(38 - 3 = 35 = 5 \cdot 7\), oraz \(-17 \equiv 4 \pmod{7}\), bo \(-17 - 4 = -21\). Natomiast \(20 \not\equiv 6 \pmod{8}\), bo różnica 14 nie dzieli się przez 8. Zapis \(a \equiv 0 \pmod{n}\) to po prostu inny zapis podzielności \(n \mid a\).
Skąd równoważność obu sformułowań? Jeśli \(a = nq_1 + r\) i \(b = nq_2 + r\) z tą samą resztą \(r\), to \(a - b = n(q_1 - q_2)\). Odwrotnie, jeśli \(a - b = nk\), to \(a = b + nk\), a dodanie wielokrotności \(n\) nie zmienia reszty.
Najlepsza intuicja to zegar. Tarcza liczy godziny modulo 12: jeśli jest godzina 9, to za 100 godzin wskazówka wykona \(100 = 8 \cdot 12 + 4\), czyli osiem pełnych obrotów i jeszcze cztery godziny. Wskaże więc \(9 + 100 = 109 \equiv 1 \pmod{12}\), czyli godzinę 1. Pełne obroty nie mają znaczenia — liczy się tylko reszta.
Wszystkie liczby całkowite rozpadają się modulo \(n\) na \(n\) klas reszt. Modulo 12 klasa jedynki to \(\ldots, -23, -11, 1, 13, 25, \ldots, 109, \ldots\) — liczby, które na tarczy trafiają w to samo miejsce. Każda klasa ma dokładnie jednego przedstawiciela wśród liczb \(0, 1, \ldots, n - 1\) i to on jest resztą. W rachunkach wolno jednak używać dowolnego przedstawiciela, a najwygodniejsze bywają liczby ujemne: \(11 \equiv -1 \pmod{12}\), \(6 \equiv -1 \pmod{7}\), \(99 \equiv -1 \pmod{100}\).
Działania na kongruencjach — dodawanie, mnożenie, potęgowanie
Uzasadnienie jest krótkie. Dla sumy: \((a + c) - (b + d) = (a - b) + (c - d)\), a obie różnice dzielą się przez \(n\). Dla iloczynu:
i znów oba składniki dzielą się przez \(n\). Potęga to wielokrotny iloczyn, więc wynika z poprzedniego punktu. Praktyczny wniosek: w wyrażeniu zbudowanym z dodawania, odejmowania, mnożenia i potęg o ustalonych wykładnikach każdą liczbę możesz zastąpić dowolną liczbą do niej przystającą. Wykładników nie wolno przy tym redukować modulo \(n\) — do tego wrócimy przy twierdzeniu Fermata.
Przykład: jaką resztę z dzielenia przez 9 daje liczba \(2026 \cdot 2027 + 2028^2\)? Liczba i jej suma cyfr dają tę samą resztę z dzielenia przez 9, więc \(2026 \equiv 1\), \(2027 \equiv 2\), \(2028 \equiv 3 \pmod{9}\). Stąd wyrażenie przystaje do \(1 \cdot 2 + 3^2 = 11 \equiv 2 \pmod{9}\). Reszta wynosi 2 i nie trzeba było mnożyć czterocyfrowych liczb.
Drugi przykład pokazuje siłę przedstawiciela \(-1\). Ponieważ \(10 \equiv -1 \pmod{11}\), mamy \(10^{2027} \equiv (-1)^{2027} = -1 \equiv 10 \pmod{11}\). Ta sama obserwacja tłumaczy cechę podzielności przez 11: cyfra stojąca przy \(10^k\) wchodzi do reszty ze znakiem \((-1)^k\).
Kiedy wolno dzielić kongruencję
Dodawać, odejmować i mnożyć stronami wolno zawsze, ale dzielić — nie zawsze. Mamy \(14 \equiv 4 \pmod{10}\), a po podzieleniu obu stron przez 2 wychodzi \(7 \equiv 2 \pmod{10}\), co jest fałszem. Podobnie \(2 \cdot 4 \equiv 2 \cdot 1 \pmod{6}\), ale \(4 \not\equiv 1 \pmod{6}\).
Uzasadnienie: \(n \mid c(a - b)\), a skoro \(n\) nie ma z \(c\) wspólnych czynników pierwszych, wszystkie czynniki pierwsze \(n\) muszą siedzieć w \(a - b\). W przykładzie z \(14 \equiv 4 \pmod{10}\) mamy \(c = 2\), \(d = 2\), więc poprawny wniosek to \(7 \equiv 2 \pmod{5}\).
Tabliczka mnożenia modulo n
Reszt modulo \(n\) jest skończenie wiele, więc całe dodawanie i mnożenie można zapisać w tabelce. Tabliczka mnożenia modulo 7 pokazuje dwie rzeczy, które za chwilę staną się twierdzeniami.
- W każdym wierszu poza zerowym występuje każda z reszt \(1, 2, \ldots, 6\) dokładnie raz. Gdyby \(ka \equiv kb \pmod{7}\) dla \(k \not\equiv 0\), to po skróceniu (7 jest pierwsza) \(a \equiv b\).
- W każdym takim wierszu stoi jedynka, więc każda niezerowa reszta ma odwrotność: \(1 \cdot 1 \equiv 1\), \(2 \cdot 4 \equiv 1\), \(3 \cdot 5 \equiv 1\), \(6 \cdot 6 \equiv 1 \pmod{7}\).
Modulo liczba złożona tak nie jest. Wiersz dwójki w tabliczce modulo 6 to 0, 2, 4, 0, 2, 4 — jedynki brak, więc 2 nie ma odwrotności modulo 6, a do tego \(2 \cdot 3 \equiv 0 \pmod{6}\), choć żaden czynnik nie przystaje do zera.
Reszty kwadratów i sześcianów — lista do zapamiętania
Żeby poznać możliwe reszty \(x^2\) modulo \(n\), wystarczy podstawić \(x = 0, 1, \ldots, n - 1\), a nawet tylko połowę z nich, bo \((-x)^2 = x^2\). Wyniki, które wracają w zadaniach:
- kwadraty modulo 3: 0, 1 (bo \(2^2 = 4 \equiv 1\));
- kwadraty modulo 4: 0, 1 — kwadrat liczby parzystej przystaje do 0, nieparzystej do 1;
- kwadraty modulo 5: 0, 1, 4;
- kwadraty modulo 8: 0, 1, 4, przy czym kwadrat liczby nieparzystej zawsze przystaje do 1 modulo 8, bo \((2k + 1)^2 = 4k(k + 1) + 1\), a \(k(k + 1)\) jest parzyste;
- kwadraty modulo 9: 0, 1, 4, 7;
- sześciany modulo 7: 0, 1, 6, czyli \(0\) i \(\pm 1\);
- sześciany modulo 9: 0, 1, 8, czyli \(0\) i \(\pm 1\), bo \((3k \pm 1)^3 = 27k^3 \pm 27k^2 + 9k \pm 1\).
Im mniej reszt przyjmuje kwadrat lub sześcian, tym lepszy jest dany moduł do dowodów, że równanie nie ma rozwiązań. Stąd popularność modułów 3, 4 i 8 dla kwadratów oraz 7 i 9 dla sześcianów.
Ostatnia cyfra potęgi i cykle reszt
Ostatnia cyfra liczby naturalnej to jej reszta z dzielenia przez 10. Żeby znaleźć ostatnią cyfrę potęgi, wystarczy więc mnożyć same ostatnie cyfry. Dla siódemki: \(7\), \(7 \cdot 7 = 49\) (cyfra 9), \(9 \cdot 7 = 63\) (cyfra 3), \(3 \cdot 7 = 21\) (cyfra 1), \(1 \cdot 7 = 7\) — i cykl się zamyka. Ostatnie cyfry potęg \(7^n\) powtarzają się z okresem 4: 7, 9, 3, 1.
Ostatnia cyfra liczby \(7^{2026}\): ponieważ \(2026 = 4 \cdot 506 + 2\), mamy
Okresy ostatnich cyfr dla wszystkich cyfr:
- 0, 1, 5, 6 — każda potęga kończy się tą samą cyfrą;
- 4: 4, 6 oraz 9: 9, 1 — okres 2 (nieparzysty wykładnik daje pierwszą cyfrę, parzysty drugą);
- 2: 2, 4, 8, 6; 3: 3, 9, 7, 1; 7: 7, 9, 3, 1; 8: 8, 4, 2, 6 — okres 4.
Ta sama metoda działa dla dowolnego modułu. Szczególnie opłaca się szukać potęgi przystającej do \(-1\), bo skraca rachunek o połowę. Reszta z dzielenia \(5^{2026}\) przez 13: \(5^2 = 25 \equiv -1 \pmod{13}\), więc \(5^4 \equiv 1\). Z \(2026 = 4 \cdot 506 + 2\) dostajemy \(5^{2026} \equiv 5^2 \equiv -1 \equiv 12 \pmod{13}\).
Małe twierdzenie Fermata i twierdzenie Eulera
Cykle potęg mają długość, której nie trzeba zgadywać. Dla modułu pierwszego daje ją jedno z najważniejszych twierdzeń teorii liczb.
Idea dowodu. Rozważ liczby \(a, 2a, 3a, \ldots, (p - 1)a\). Żadna nie dzieli się przez \(p\), bo \(p\) jest pierwsza i nie dzieli żadnego z czynników. Żadne dwie nie przystają do siebie: z \(ia \equiv ja\) po skróceniu przez \(a\) (wolno, bo \(\text{NWD}(a, p) = 1\)) wynika \(i \equiv j\). Mamy więc \(p - 1\) różnych niezerowych reszt, czyli wszystkie reszty \(1, 2, \ldots, p - 1\) w innej kolejności. Dla \(p = 7\) i \(a = 3\) liczby \(3, 6, 9, 12, 15, 18\) dają reszty 3, 6, 2, 5, 1, 4 — to dokładnie wiersz trójki w tabliczce mnożenia modulo 7. Mnożąc wszystkie te liczby, dostajemy
Liczba \((p - 1)!\) jest względnie pierwsza z \(p\), więc wolno przez nią skrócić: \(a^{p - 1} \equiv 1 \pmod{p}\). Wersję \(a^p \equiv a\) dostajemy, mnożąc przez \(a\), a gdy \(p \mid a\), obie strony przystają do zera.
Zastosowanie: reszta z dzielenia \(3^{100}\) przez 7. Z twierdzenia Fermata \(3^6 \equiv 1 \pmod{7}\), a \(100 = 6 \cdot 16 + 4\), więc \(3^{100} \equiv 3^4 = 81 \equiv 4 \pmod{7}\). Ogólnie: gdy \(p \nmid a\), wykładnik wolno redukować modulo \(p - 1\) — nie modulo \(p\).
Twierdzenia nie da się odwrócić. Liczba \(341 = 11 \cdot 31\) jest złożona, a mimo to \(2^{340} \equiv 1 \pmod{341}\). Fermat służy więc do wykazywania, że liczba jest złożona: \(2^{14} \equiv 4 \pmod{15}\), a nie 1, zatem 15 nie może być pierwsza. Do dowodu pierwszości się nie nadaje.
Twierdzenie Eulera i funkcja φ(n)
Twierdzenie Fermata mówi tylko o modułach pierwszych. Dla dowolnego modułu jego rolę przejmuje twierdzenie Eulera.
Przykłady: \(\varphi(p) = p - 1\) dla liczby pierwszej \(p\); \(\varphi(10) = 4\) (liczby 1, 3, 7, 9); \(\varphi(12) = 4\) (liczby 1, 5, 7, 11); \(\varphi(9) = 6\); \(\varphi(100) = 100 \cdot \frac{1}{2} \cdot \frac{4}{5} = 40\).
Dowód jest ten sam co u Fermata: mnożenie przez \(a\) przestawia \(\varphi(n)\) reszt względnie pierwszych z \(n\), a ich iloczyn można skrócić. Twierdzenie tłumaczy cykle ostatnich cyfr: \(\varphi(10) = 4\), więc dla cyfr 1, 3, 7, 9 mamy \(a^4 \equiv 1 \pmod{10}\). Cyfry 2, 4, 5, 6, 8 nie są względnie pierwsze z 10 — dlatego cykle dwójki i ósemki nie przechodzą przez jedynkę.
Rzeczywisty okres może być krótszy niż \(\varphi(n)\), ale zawsze jest jego dzielnikiem. Dwie ostatnie cyfry liczby \(13^{2026}\): \(\varphi(100) = 40\), więc wystarczy znać \(13^{26}\), bo \(2026 = 40 \cdot 50 + 26\). Liczymy kolejne kwadraty modulo 100: \(13^2 = 169 \equiv 69\), \(13^4 \equiv 69^2 = 4761 \equiv 61\), \(13^5 \equiv 61 \cdot 13 = 793 \equiv 93\), \(13^{10} \equiv 93^2 = 8649 \equiv 49\), \(13^{20} \equiv 49^2 = 2401 \equiv 1\). Okres wynosi tu 20, więc \(13^{2026} \equiv 13^6 = 13^4 \cdot 13^2 \equiv 61 \cdot 69 = 4209 \equiv 9 \pmod{100}\). Liczba \(13^{2026}\) kończy się cyframi 09.
Odwrotność modulo, kongruencje liniowe i chińskie twierdzenie o resztach
Odwrotność i rozszerzony algorytm Euklidesa
Dla małych modułów odwrotność odczytasz z tabliczki (modulo 7 odwrotnością 3 jest 5). Dla większych służy rozszerzony algorytm Euklidesa: liczymy NWD, a potem cofamy się, zapisując 1 jako kombinację \(a\) i \(n\). Odwrotność 5 modulo 17: \(17 = 3 \cdot 5 + 2\) oraz \(5 = 2 \cdot 2 + 1\), więc
Stąd \(5 \cdot 7 \equiv 1 \pmod{17}\); rzeczywiście \(35 = 2 \cdot 17 + 1\).
Trzy przypadki:
- \(5x \equiv 3 \pmod{17}\): mnożymy przez odwrotność 5, czyli 7, i dostajemy \(x \equiv 21 \equiv 4 \pmod{17}\). Sprawdzenie: \(5 \cdot 4 = 20 \equiv 3\).
- \(6x \equiv 9 \pmod{15}\): \(d = 3\) dzieli 9, więc \(2x \equiv 3 \pmod{5}\). Odwrotnością 2 modulo 5 jest 3, zatem \(x \equiv 9 \equiv 4 \pmod{5}\), czyli modulo 15 są trzy rozwiązania: \(x \equiv 4, 9, 14\).
- \(6x \equiv 8 \pmod{15}\): \(d = 3\) nie dzieli 8, więc rozwiązań nie ma — liczba \(6x - 8\) daje przy dzieleniu przez 3 resztę 1, a więc nie może być wielokrotnością 15.
Chińskie twierdzenie o resztach
Dlaczego to działa dla dwóch modułów, widać na przykładzie 5 i 7. Każdej liczbie \(x\) od 0 do 34 przypisujemy parę reszt \((x \bmod 5,\ x \bmod 7)\). Gdyby dwie różne liczby z tego zakresu miały tę samą parę, ich różnica dzieliłaby się przez 5 i przez 7, czyli przez 35 — niemożliwe, bo jest mniejsza od 35. Liczb jest 35 i par jest 35, więc każda para reszt pojawia się dokładnie raz.
W praktyce układ rozwiązujemy podstawianiem. Niech \(x \equiv 2 \pmod{5}\) i \(x \equiv 3 \pmod{7}\). Z pierwszej kongruencji \(x = 5k + 2\). Podstawiamy do drugiej: \(5k + 2 \equiv 3\), czyli \(5k \equiv 1 \pmod{7}\). Odwrotnością 5 modulo 7 jest 3 (\(15 \equiv 1\)), więc \(k \equiv 3 \pmod{7}\), \(k = 7m + 3\) i \(x = 35m + 17\). Odpowiedź: \(x \equiv 17 \pmod{35}\). Na rysunku liczby od 0 do 34 są rozmieszczone według par reszt: wiersz to reszta z dzielenia przez 5, kolumna — reszta z dzielenia przez 7. Kolejne liczby wędrują po przekątnych i zapełniają każde z 35 pól dokładnie raz, a liczba 17 stoi w wierszu 2 i kolumnie 3.
Gdy moduły nie są względnie pierwsze, układ może być sprzeczny: \(x \equiv 1 \pmod{4}\) mówi, że \(x\) jest nieparzyste, a \(x \equiv 2 \pmod{6}\) — że parzyste. Ogólnie układ dwóch kongruencji ma rozwiązanie dokładnie wtedy, gdy \(r_1 \equiv r_2 \pmod{\text{NWD}(n_1, n_2)}\).
Reszty w dowodach — brak rozwiązań całkowitych i podzielność
Jak udowodnić, że równanie nie ma rozwiązań całkowitych
Jeśli liczby całkowite spełniają równanie \(L = P\), to spełniają też \(L \equiv P \pmod{n}\) dla każdego modułu \(n\). Wystarczy więc znaleźć jeden moduł, dla którego zbiory możliwych reszt lewej i prawej strony są rozłączne. To dowód nie wprost; jak go starannie zapisać, pokazuje lekcja dowody na maturze — nierówności, podzielność, dowód nie wprost.
Dwa szybkie przykłady:
- \(x^2 + y^2 = 2027\) nie ma rozwiązań: kwadraty modulo 4 to 0 lub 1, więc suma dwóch kwadratów przystaje do 0, 1 albo 2, a \(2027 \equiv 3 \pmod{4}\). Ogólnie żadna liczba postaci \(4k + 3\) nie jest sumą dwóch kwadratów.
- \(x^2 - 3y^2 = 2\) nie ma rozwiązań: modulo 3 lewa strona przystaje do \(x^2\), czyli do 0 albo 1, a prawa do 2.
Podzielność wyrażeń typu n⁵ − n
Wersja \(a^p \equiv a \pmod{p}\) twierdzenia Fermata od razu daje podzielność wielu wyrażeń. Na przykład \(n^5 \equiv n \pmod{5}\), więc \(5 \mid n^5 - n\) dla każdej liczby całkowitej \(n\). Rozkład z wzorów skróconego mnożenia
zawiera trzy kolejne liczby całkowite, więc wyrażenie dzieli się też przez 2 i przez 3.
Gdy chcesz sprawdzić podzielność przez małą liczbę bez twierdzeń, zawsze działa przegląd reszt: podstaw za \(n\) każdą resztę modulo \(m\) i sprawdź, że wyrażenie przystaje do zera. Dla modułów do kilkunastu to kilka linijek rachunku i w pełni poprawny dowód.
Przykłady rozwiązane krok po kroku
Przykład 1 (PP) — reszta z dzielenia bez liczenia iloczynu
Jaką resztę z dzielenia przez 11 daje liczba \(1000 \cdot 1001 + 2026^2\)?
Rozwiązanie. \(1001 = 11 \cdot 91\), więc \(1001 \equiv 0 \pmod{11}\) i cały pierwszy składnik przystaje do zera, niezależnie od czynnika 1000. Dalej \(2026 = 11 \cdot 184 + 2\), czyli \(2026 \equiv 2\) i \(2026^2 \equiv 4 \pmod{11}\). Reszta wynosi 4. Nie trzeba było obliczać \(2026^2 = 4\,104\,676\).
Przykład 2 (PP) — ostatnia cyfra sumy potęg
Wyznacz ostatnią cyfrę liczby \(2^{2026} + 3^{2026} + 4^{2026}\).
Rozwiązanie. Liczymy modulo 10. Wykładnik \(2026 = 4 \cdot 506 + 2\), więc dla cykli długości 4 bierzemy drugi wyraz: cykl dwójki 2, 4, 8, 6 daje 4, cykl trójki 3, 9, 7, 1 daje 9. Cykl czwórki 4, 6 ma długość 2, a wykładnik jest parzysty, więc \(4^{2026}\) kończy się szóstką. Suma ostatnich cyfr to \(4 + 9 + 6 = 19\), więc szukana cyfra to 9.
Przykład 3 (PR) — reszta z małego twierdzenia Fermata
Wykaż, że liczba \(2^{1000} - 3\) jest podzielna przez 13.
Rozwiązanie. 13 jest liczbą pierwszą i nie dzieli 2, więc \(2^{12} \equiv 1 \pmod{13}\). Dzielimy wykładnik: \(1000 = 12 \cdot 83 + 4\). Zatem
czyli \(2^{1000} - 3 \equiv 0 \pmod{13}\). Okres jest tu rzeczywiście równy 12, a nie krótszy: \(2^6 = 64 = 65 - 1 \equiv -1 \pmod{13}\), więc dopiero dwunasta potęga daje 1.
Przykład 4 (PR) — dwie ostatnie cyfry potęgi
Wyznacz dwie ostatnie cyfry liczby \(7^{2026}\).
Rozwiązanie. Liczymy modulo 100. Twierdzenie Eulera daje \(7^{40} \equiv 1\), ale warto najpierw spróbować małych potęg: \(7^2 = 49\), \(7^4 = 49^2 = 2401 \equiv 1 \pmod{100}\). Okres wynosi 4 (dzielnik liczby 40). Z \(2026 = 4 \cdot 506 + 2\) mamy \(7^{2026} \equiv 7^2 = 49 \pmod{100}\). Liczba \(7^{2026}\) kończy się cyframi 49. Zgadza się to z przykładem z cyklem ostatnich cyfr: ostatnia cyfra to 9.
Przykład 5 (PR) — kongruencja liniowa rozszerzonym algorytmem Euklidesa
Rozwiąż kongruencję \(17x \equiv 5 \pmod{43}\) i podaj jej najmniejsze rozwiązanie trzycyfrowe.
Rozwiązanie. 43 jest pierwsza, więc 17 ma odwrotność. Algorytm Euklidesa:
Cofamy się: \(1 = 9 - 8 = 9 - (17 - 9) = 2 \cdot 9 - 17 = 2 \cdot (43 - 2 \cdot 17) - 17 = 2 \cdot 43 - 5 \cdot 17\). Stąd \(17 \cdot (-5) \equiv 1 \pmod{43}\), czyli odwrotnością 17 jest \(-5 \equiv 38\). Mnożymy kongruencję przez \(-5\): \(x \equiv -25 \equiv 18 \pmod{43}\). Sprawdzenie: \(17 \cdot 18 = 306 = 7 \cdot 43 + 5\). Rozwiązania to \(18, 61, 104, \ldots\), więc najmniejsze trzycyfrowe to 104.
Przykład 6 (PR) — chińskie twierdzenie o resztach w zadaniu tekstowym
W pudełku jest od 200 do 400 kulek. Przy pakowaniu po 4 zostaje 1 kulka, po 5 — zostają 2, a po 9 — zostaje 5. Ile kulek jest w pudełku?
Rozwiązanie. Szukamy \(x\), dla którego \(x \equiv 1 \pmod{4}\), \(x \equiv 2 \pmod{5}\), \(x \equiv 5 \pmod{9}\). Moduły są parami względnie pierwsze, więc rozwiązanie jest jedno modulo \(4 \cdot 5 \cdot 9 = 180\). Zaczynamy od największego modułu: \(x = 9k + 5\). Modulo 4: \(9k + 5 \equiv k + 1 \equiv 1\), więc \(k \equiv 0 \pmod{4}\), \(k = 4m\) i \(x = 36m + 5\). Modulo 5: \(36m + 5 \equiv m \equiv 2\), więc \(m = 5t + 2\) i
Sprawdzenie dla 77: \(77 = 4 \cdot 19 + 1 = 5 \cdot 15 + 2 = 9 \cdot 8 + 5\). W przedziale od 200 do 400 leży tylko \(77 + 180 = 257\). W pudełku jest 257 kulek.
Przykład 7 (PR) — suma trzech kwadratów i moduł 8
Wykaż, że równanie \(x^2 + y^2 + z^2 = 2031\) nie ma rozwiązań w liczbach całkowitych.
Rozwiązanie. Moduł 4 nie wystarczy: \(2031 \equiv 3 \pmod{4}\), a \(1 + 1 + 1 = 3\), więc reszty się nie wykluczają. Bierzemy moduł 8, przy którym kwadraty przystają do 0, 1 lub 4. Sumy trzech takich reszt to: \(0, 1, 2, 3\) (same zera i jedynki), \(4, 5, 6\) (jedna czwórka), \(8 \equiv 0\), \(9 \equiv 1\) (dwie czwórki) i \(12 \equiv 4\) (trzy czwórki). Reszta 7 nie pojawia się nigdy. Tymczasem \(2031 = 8 \cdot 253 + 7\), więc równanie nie ma rozwiązań całkowitych. Wniosek ogólny: liczba postaci \(8k + 7\) nie jest sumą trzech kwadratów.
Przykład 8 (OM) — suma trzech sześcianów i moduł 9
Wykaż, że równanie \(x^3 + y^3 + z^3 = 2030\) nie ma rozwiązań w liczbach całkowitych.
Rozwiązanie. Sześciany modulo 9 przystają do \(0\), \(1\) lub \(-1\), więc suma trzech sześcianów przystaje do jednej z liczb od \(-3\) do \(3\), czyli do reszty 0, 1, 2, 3, 6, 7 albo 8. Reszty 4 i 5 są niemożliwe. Ponieważ \(2030 = 9 \cdot 225 + 5\), równanie nie ma rozwiązań. Moduł 7 by tu nie pomógł: sześciany modulo 7 też przystają do 0 lub \(\pm 1\), ale sumy od \(-3\) do \(3\) pokrywają wszystkie siedem reszt.
Przykład 9 (OM) — podzielność sumy sześcianów przez 7
Wykaż, że jeśli \(7 \mid x^3 + y^3 + z^3\) dla liczb całkowitych \(x, y, z\), to co najmniej jedna z nich jest podzielna przez 7.
Rozwiązanie. Przypuśćmy, że żadna z liczb nie dzieli się przez 7. Wtedy każdy sześcian przystaje do \(1\) albo \(-1\) modulo 7, więc \(x^3 + y^3 + z^3 \equiv s \pmod{7}\), gdzie \(s\) jest sumą trzech liczb \(\pm 1\). Taka suma jest nieparzysta i wynosi \(-3\), \(-1\), \(1\) albo \(3\) — żadna z tych liczb nie dzieli się przez 7. Zatem \(x^3 + y^3 + z^3 \not\equiv 0 \pmod{7}\), sprzeczność z założeniem. Kontrprzykład z dwiema liczbami pokazuje, że trzy składniki są istotne: \(1^3 + 6^3 = 217 = 7 \cdot 31\), a ani 1, ani 6 nie dzieli się przez 7.
Przykład 10 (PR, OM) — liczba n⁷ − n
Wykaż, że \(42 \mid n^7 - n\) dla każdej liczby całkowitej \(n\). Znajdź analogiczny dzielnik dla \(n^{13} - n\).
Rozwiązanie. \(42 = 2 \cdot 3 \cdot 7\). Korzystamy z uogólnienia twierdzenia Fermata: wykładnik \(k = 7\) spełnia \((p - 1) \mid 6\) dla \(p = 2\), \(p = 3\) i \(p = 7\). Bezpośrednio: z \(n^7 \equiv n \pmod{7}\) mamy podzielność przez 7; z \(n^3 \equiv n \pmod{3}\) wynika \(n^7 = n^3 \cdot n^3 \cdot n \equiv n \cdot n \cdot n = n^3 \equiv n \pmod{3}\); z \(n^2 \equiv n \pmod{2}\) wynika, że każda potęga \(n\) ma tę samą parzystość co \(n\). Liczby 2, 3 i 7 są parami względnie pierwsze, więc \(42 \mid n^7 - n\).
Dla \(n^{13} - n\) szukamy liczb pierwszych \(p\), dla których \(p - 1\) dzieli 12: to \(p = 2, 3, 5, 7, 13\). Zatem \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 13 = 2730\) dzieli \(n^{13} - n\) dla każdego \(n\). Jest to największy taki dzielnik: \(\text{NWD}(2^{13} - 2,\ 3^{13} - 3) = \text{NWD}(8190,\ 1\,594\,320) = 2730\).
Przykład 11 (OM) — kiedy 13 dzieli 2ⁿ + 3ⁿ
Wyznacz wszystkie liczby naturalne \(n\), dla których \(13 \mid 2^n + 3^n\).
Rozwiązanie. Modulo 13 odwrotnością 2 jest 7 (\(14 \equiv 1\)). Mnożąc warunek \(3^n \equiv -2^n\) przez \(7^n\), dostajemy \((3 \cdot 7)^n \equiv -(2 \cdot 7)^n \equiv -1\), a ponieważ \(21 \equiv 8\), warunek ma postać
Potęgi ósemki modulo 13: \(8^1 \equiv 8\), \(8^2 = 64 \equiv -1\), \(8^3 \equiv -8 \equiv 5\), \(8^4 \equiv 1\). Okres wynosi 4, a \(-1\) pojawia się tylko na drugim miejscu cyklu. Odpowiedź: \(n \equiv 2 \pmod{4}\), czyli \(n = 2, 6, 10, \ldots\). Kontrola: \(2^2 + 3^2 = 13\) oraz \(2^6 + 3^6 = 64 + 729 = 793 = 13 \cdot 61\). Pomysł „podziel przez jedną z potęg” zamienia sumę dwóch potęg w jedną potęgę i bardzo często skraca zadania olimpijskie.
Przykład 12 (OM) — liczba złożona z samych jedynek
Wykaż, że dla każdej liczby pierwszej \(p \geq 7\) liczba zapisana za pomocą \(p - 1\) jedynek jest podzielna przez \(p\).
Rozwiązanie. Liczba złożona z \(p - 1\) jedynek to
Liczba pierwsza \(p \geq 7\) nie dzieli 10, więc z twierdzenia Fermata \(10^{p - 1} \equiv 1 \pmod{p}\), czyli \(p \mid 9R\). Ponieważ \(p \neq 3\), liczby \(p\) i 9 są względnie pierwsze, więc \(p \mid R\). Dla \(p = 7\): \(111\,111 = 7 \cdot 15\,873\); dla \(p = 13\) liczba z dwunastu jedynek to \(13 \cdot 8\,547\,008\,547\). Założenie \(p \neq 3\) jest potrzebne: liczba 11 nie dzieli się przez 3.
Typowe błędy
- Dzielenie kongruencji przez liczbę, która ma wspólny dzielnik z modułem. Z \(14 \equiv 4 \pmod{10}\) nie wynika \(7 \equiv 2 \pmod{10}\), tylko \(7 \equiv 2 \pmod{5}\). Skracać wolno tylko przez liczby względnie pierwsze z modułem, w przeciwnym razie trzeba podzielić także moduł.
- Ujemna reszta w odpowiedzi. W rachunkach \(-3\) i \(4\) są równie dobre modulo 7, ale resztą z dzielenia \(-17\) przez 7 jest 4, nie \(-3\). Odpowiedź końcową zawsze sprowadzaj do zakresu od 0 do \(n - 1\).
- Redukcja wykładnika modulo n. \(2^{10} \not\equiv 2^3 \pmod{7}\): \(2^{10} = 1024 \equiv 2\), a \(2^3 = 8 \equiv 1\). Wykładnik redukuje się modulo okres (dla modułu pierwszego \(p\) — modulo \(p - 1\)), nigdy modulo sam moduł.
- Twierdzenie Fermata bez założeń. Gdy \(p \mid a\), to \(a^{p - 1} \equiv 0\), a nie 1 (np. \(7^6 \equiv 0 \pmod{7}\)). Dla modułu złożonego twierdzenie nie działa: \(2^8 = 256 \equiv 4 \pmod{9}\) — tu trzeba użyć \(\varphi(9) = 6\).
- Zerowe miejsce w cyklu. Gdy wykładnik dzieli się przez okres, bierz ostatni wyraz cyklu: \(2^{2024}\) kończy się szóstką, a nie jedynką.
- Pochopny wniosek z reszty kwadratu. Z \(x^2 \equiv 1 \pmod{8}\) nie wynika \(x \equiv 1\) — każda liczba nieparzysta to spełnia. Z \(x^2 \equiv 0 \pmod{4}\) wynika tylko, że \(x\) jest parzyste.
- Chińskie twierdzenie dla modułów, które nie są względnie pierwsze. Układ \(x \equiv 1 \pmod{4}\), \(x \equiv 2 \pmod{6}\) jest sprzeczny; zawsze najpierw sprawdź NWD modułów.
- Za słaby moduł. Gdy reszty nie dały sprzeczności, nie znaczy to, że rozwiązanie istnieje — moduł 4 nie rozstrzyga przykładu 7, a moduł 8 tak.
Ściąga — kongruencje w pigułce
- \(a \equiv b \pmod{n}\) oznacza \(n \mid a - b\), czyli tę samą resztę z dzielenia przez \(n\).
- Kongruencje można dodawać, odejmować, mnożyć i podnosić do potęgi stronami; dzielić tylko przez liczby względnie pierwsze z modułem.
- Wygodni przedstawiciele: \(n - 1 \equiv -1\), np. \(10 \equiv -1 \pmod{11}\), \(6 \equiv -1 \pmod{7}\).
- Ostatnia cyfra to reszta modulo 10; okresy ostatnich cyfr potęg mają długość 1, 2 lub 4.
- Fermat: \(p\) pierwsza, \(p \nmid a\) daje \(a^{p - 1} \equiv 1 \pmod{p}\); zawsze \(a^p \equiv a \pmod{p}\).
- Euler: \(\text{NWD}(a, n) = 1\) daje \(a^{\varphi(n)} \equiv 1 \pmod{n}\); \(\varphi(10) = 4\), \(\varphi(100) = 40\); okres dzieli \(\varphi(n)\).
- Odwrotność \(a\) modulo \(n\) istnieje, gdy \(\text{NWD}(a, n) = 1\); znajdziesz ją rozszerzonym algorytmem Euklidesa.
- \(ax \equiv b \pmod{n}\) ma rozwiązanie, gdy \(d = \text{NWD}(a, n)\) dzieli \(b\); jest ich wtedy \(d\) modulo \(n\).
- Chińskie twierdzenie: moduły parami względnie pierwsze dają jedno rozwiązanie modulo iloczyn; rozwiązuj podstawianiem.
- Kwadraty: modulo 3 i 4 tylko 0, 1; modulo 8 tylko 0, 1, 4. Sześciany: modulo 7 i 9 tylko 0, \(\pm 1\).
- \(p \mid n^k - n\), gdy \((p - 1) \mid (k - 1)\); stąd \(5 \mid n^5 - n\), \(42 \mid n^7 - n\) i \(2730 \mid n^{13} - n\).
Sprawdź się
Najpierw kilka szybkich zadań (odpowiedzi w nawiasach):
- Jaką resztę z dzielenia przez 8 daje \(3^{50}\)? (1, bo \(3^2 = 9 \equiv 1\))
- Jaka jest ostatnia cyfra liczby \(8^{2027}\)? (2, bo \(2027 = 4 \cdot 506 + 3\))
- Rozwiąż \(4x \equiv 6 \pmod{10}\). (\(x \equiv 4 \pmod{5}\), czyli \(x \equiv 4\) lub \(9 \pmod{10}\))
- Rozwiąż układ \(x \equiv 3 \pmod{4}\), \(x \equiv 4 \pmod{9}\). (\(x \equiv 31 \pmod{36}\))
- Wykaż, że równanie \(x^2 = 5y + 3\) nie ma rozwiązań całkowitych. (kwadraty modulo 5 to 0, 1, 4)
- Wykaż, że \(11 \mid 6^{2n} + 3^{n + 2} + 3^n\) dla każdej liczby naturalnej \(n\). (\(36 \equiv 3 \pmod{11}\), więc wyrażenie przystaje do \(11 \cdot 3^n\))
Potem zadania z bazy, od prostszych do trudniejszych:
- Suma liczb dwucyfrowych dających resztę 3 z dzielenia przez 7 — klasa reszt modulo 7 jako ciąg arytmetyczny.
- Reszta z dzielenia potęgi dwójki przez 7 — metoda cyklu albo twierdzenie Fermata.
- Cyfra jedności wyrazu a₂₀₂₆ ciągu aₙ₊₁ = 3aₙ − 4 z a₁ = 5 — rekurencja modulo 10 i okres ostatnich cyfr.
- Najmniejsza wielokrotność 11 z resztami 3, 4, 5 przy dzieleniu przez 4, 5, 6 — układ kongruencji jak w przykładzie 6.
- Największa liczba dzieląca n⁵ − n dla każdego całkowitego n — Fermat i rozkład na czynniki, jak w przykładzie 10.
- Podzielność n² + 20 przez n + 2 — modulo \(n + 2\) mamy \(n \equiv -2\).
- Dwie ostatnie cyfry wieży potęg trójki — twierdzenie Eulera modulo 100 i okres wykładnika.
Więcej zadań znajdziesz w działach teoria liczb i zadania olimpijskie, a informacje o zawodach i archiwalne zadania — na stronie Olimpiada Matematyczna.
Dalszy ciąg tej historii: reszty modulo liczba pierwsza tworzą ciało, z którego budowane są kody korekcyjne — zobacz lekcję ciała skończone i kod Hamminga, a małe twierdzenie Fermata jako wniosek z twierdzenia Lagrange’a — w lekcji grupy, permutacje i twierdzenie Lagrange’a.
Zadania w stylu Olimpiady Matematycznej, w których ta technika jest kluczem:
- Reszta iloczynu (k⁴ + 1) dla k od 1 do 100 przy dzieleniu przez 101
- Sześciany 1³, 2³, …, n³ dające parami różne reszty z dzielenia przez n
- Ile liczb n ≤ 2026 ma tę własność, że 8^n − n dzieli się przez 11
- Najmniejsze l, dla którego 2^l − 9 dzieli się przez 289
- Trójki reszt modulo 13 z zerową sumą i zerową sumą piątych potęg
- Trójki o sumie 23, dla których 11 dzieli a³ + b³ + c³ − 1
Dzisiejszy zestaw zadań → Trening liczenia w pamięci · 2 min