Teoria liczb

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}\).

Tarcza zegara jako reszty modulo 12: od godziny 9 po 100 godzinach, czyli 8 pełnych obrotach i 4 godzinach, wskazówka trafia na 101234567891011+49 + 100 = 109100 = 8 · 12 + 4109 ≡ 1 (mod 12)klasa reszty 1:…, −23, −11, 1, 13, 25, …pełne obroty (wielokrotności 12)nie zmieniają wskazania
Zegar liczy modulo 12: od godziny 9 po 100 godzinach (\(100 = 8 \cdot 12 + 4\)) wskazówka staje na 1, bo \(109 \equiv 1 \pmod{12}\)

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:

\[ ac - bd = a(c - d) + d(a - b), \]

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.

Tabliczka mnożenia modulo 7: w każdym niezerowym wierszu każda reszta od 1 do 6 występuje raz; jedynki wskazują pary odwrotności·001122334455660000000012345602461350362514041526305316420654321wiersz 3: 0, 3, 6, 2, 5, 1, 4 — każda niezerowa reszta razodwrotności: 1·1, 2·4, 3·5, 6·6 ≡ 1
Tabliczka mnożenia modulo 7: każdy niezerowy wiersz zawiera reszty \(1, \ldots, 6\) dokładnie raz, a jedynki wskazują odwrotności: \(2 \cdot 4 \equiv 3 \cdot 5 \equiv 6 \cdot 6 \equiv 1\)
  • 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.

Cykl ostatnich cyfr potęg siódemki: 7, 9, 3, 1 i od nowa; 7 do potęgi 2026 kończy się cyfrą 9· 7· 7· 7· 77n ≡ 1 (mod 4)9n ≡ 2 (mod 4)3n ≡ 3 (mod 4)1n ≡ 0 (mod 4)7¹ = 77² = 497³ = 3437⁴ = 24017⁵ = 168072026 = 4 · 506 + 27²⁰²⁶ kończy się cyfrą 9
Ostatnie cyfry potęg \(7^n\) tworzą cykl długości 4: \(7, 9, 3, 1\). Wykładnik \(2026\) daje resztę 2 z dzielenia przez 4, więc \(7^{2026}\) kończy się cyfrą 9

Ostatnia cyfra liczby \(7^{2026}\): ponieważ \(2026 = 4 \cdot 506 + 2\), mamy

\[ 7^{2026} = \left(7^4\right)^{506} \cdot 7^2 \equiv 1^{506} \cdot 49 \equiv 9 \pmod{10}. \]

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

\[ a \cdot 2a \cdot \ldots \cdot (p - 1)a \equiv 1 \cdot 2 \cdot \ldots \cdot (p - 1) \pmod{p}, \quad \text{czyli} \quad a^{p - 1} \cdot (p - 1)! \equiv (p - 1)! \pmod{p}. \]

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

\[ 1 = 5 - 2 \cdot 2 = 5 - 2 \cdot (17 - 3 \cdot 5) = 7 \cdot 5 - 2 \cdot 17. \]

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.

Liczby od 0 do 34 rozmieszczone według reszt z dzielenia przez 5 (wiersze) i przez 7 (kolumny); każde pole zawiera dokładnie jedną liczbę, 17 to rozwiązanie układureszta z dzielenia przez 7przez 5012345600153010255201211163111266272221732122732882331833134142992441934x ≡ 2 (mod 5) i x ≡ 3 (mod 7) ⇒ x ≡ 17 (mod 35)
Chińskie twierdzenie o resztach dla modułów 5 i 7: każda para reszt odpowiada dokładnie jednej liczbie od 0 do 34; układ \(x \equiv 2 \pmod{5}\), \(x \equiv 3 \pmod{7}\) daje \(x = 17\)

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

\[ n^5 - n = n(n^4 - 1) = (n - 1) \cdot n \cdot (n + 1) \cdot (n^2 + 1) \]

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

\[ 2^{1000} = \left(2^{12}\right)^{83} \cdot 2^4 \equiv 16 \equiv 3 \pmod{13}, \]

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:

\[ 43 = 2 \cdot 17 + 9, \quad 17 = 1 \cdot 9 + 8, \quad 9 = 1 \cdot 8 + 1. \]

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

\[ x = 36(5t + 2) + 5 = 180t + 77. \]

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ć

\[ 8^n \equiv -1 \pmod{13}. \]

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

\[ R = 11\ldots1 = \frac{10^{p - 1} - 1}{9}, \quad \text{czyli} \quad 9R = 10^{p - 1} - 1. \]

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):

  1. Jaką resztę z dzielenia przez 8 daje \(3^{50}\)? (1, bo \(3^2 = 9 \equiv 1\))
  2. Jaka jest ostatnia cyfra liczby \(8^{2027}\)? (2, bo \(2027 = 4 \cdot 506 + 3\))
  3. Rozwiąż \(4x \equiv 6 \pmod{10}\). (\(x \equiv 4 \pmod{5}\), czyli \(x \equiv 4\) lub \(9 \pmod{10}\))
  4. Rozwiąż układ \(x \equiv 3 \pmod{4}\), \(x \equiv 4 \pmod{9}\). (\(x \equiv 31 \pmod{36}\))
  5. Wykaż, że równanie \(x^2 = 5y + 3\) nie ma rozwiązań całkowitych. (kwadraty modulo 5 to 0, 1, 4)
  6. 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:

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:

Dzisiejszy zestaw zadań → Trening liczenia w pamięci · 2 min