Kongruencje, czyli czasami lepiej wiedzieć mniej

Z geometrii na pewno znacie pojęcie przystawania. W geometrii przystające (czyli jednakowe) mogą być figury. Okazuje się, że pojęcie przystawania funkcjonuje też w arytmetyce. Tu przystające mogą być liczby (i wcale nie muszą być wtedy równe, chociaż liczby równe zawsze są przystające). Ideę przystawania liczb wykorzystamy do rozwiązywania rozmaitych zadań.

Gdy rozwiązujemy zadania z arytmetyki lub szkolnej algebry, zwykle interesuje nas to, czy jakieś liczby są równe, jednak to podejście nie zawsze jest optymalne. Zdarza się to zwłaszcza w zadaniach, w których musimy udowodnić, że dane równanie nie jest spełnione przez żadną liczbę całkowitą.

Przykład 1. Znajdź wszystkie liczby całkowite spełniające równanie 2x = 4x–1.
Rozwiązanie. W tym równaniu lewa strona jest zawsze parzysta, a prawa - nieparzysta, czyli liczby po obu stronach znaku równości mają zawsze inną parzystość (tzn. nigdy nie są przystające ze względu na podzielność przez 2), zatem pierwiastków całkowitych to równanie mieć nie może.

Przystawanie liczb modulo n

Podczas dzielenia liczb całkowitych przez 2 można otrzymać dwie możliwe reszty 0 lub 1. Liczba parzysta to taka, która jest podzielna przez 2 (innymi słowy daje z dzielenia przez 2 resztę 0). Liczba nieparzysta nie jest podzielna przez dwa (czyli po podzieleniu jej przez 2 otrzymamy resztę 1). Reszty z dzielenia liczb całkowitych mają bardzo przydatne własności.

Ćwiczenie 1.  Podziel z resztą liczbę 2022 przez:
a) 2, b) 3, c) 10.

Jeśli dwie liczby a i b mają tę samą resztę z dzielenia przez n, piszemy a ≡_n b i czytamy ten napis "a przystaje modulo n do b". Na przykład wszystkie liczby parzyste są przystające modulo 2 (bo wszystkie dają resztę 0 z dzielenia przez 2). Czy wszystkie liczby nieparzyste też są przystające modulo 2? A czy wszystkie liczby parzyste są przystające modulo 4? 

Ćwiczenie 2.  Zapisz do jakich liczb przystaje liczba 2022 modulo:
a) 2, b) 3, c) 10.

Kongruencje

Każdy napis oznaczający przystawanie dwóch liczb całkowitych nazywamy kongruencją,
np. a ≡_n b to kongruencja liczb a i b modulo n. Jeżeli a ≡_n b oraz c ≡_n d, to także:

• a+c ≡_n b+d
• ac ≡_n bd
• a^k ≡_n b^k dla dowolnej liczby naturalnej k.

Innymi słowy wszystkie kongruencje (podobnie jak niektóre równania) można dodawać i mnożyć stronami (w tym mnożyć stronami przez dowolną liczbę całkowitą - dlaczego?), a także podnosić stronami do tej samej naturalnej potęgi. Pokazanie tego nie jest trudne, jednak wymaga wykonania dość żmudnych rachunków, dlatego w tym miejscu nie będziemy tych własności kongruencji dowodzili, pokażemy jedynie jak wygodnie da się je wykorzystać w rozwiązywaniu zadań.

Zadanie 1. Oblicz resztę z dzielenia 7²⁰²²  przez 6.
Rozwiązanie. 7 ≡₆ 1, więc 7²⁰²² ≡₆ 1²⁰²² = 1.

Zadanie 2. Jakie reszty z dzielenia przez 3 może mieć kwadrat liczby całkowitej?
Rozwiązanie. Liczba n przystaje modulo 3 do 0, 1 lub 2. Zatem n² przystaje modulo 3 do 0, 1 lub 4. Ale 4 ≡₃ 1, zatem kwadraty liczb całkowitych mają reszty z dzielenia przez 3 równe 0 lub 1.

Zadanie 3. Znajdź cyfrę jedności liczby [tex]7^{7^7} .[/tex]
Rozwiązanie. Cyfra jedności to reszta z dzielenia liczby przez 10. Najpierw rozważymy wykładnik. Po pierwsze 7² ≡₁₀ -1, a 7³ ≡₁₀ -7 ≡₁₀ 3. Po drugie 7⁴ = 7²·7² ≡₁₀ (-1)(-1) = 1. Widzimy, że wielokrotności czwórki w wykładniku nie mają wpływu na ostateczny wynik. Następnie zauważamy, że 7⁷ = 4k+3 (dla pewnego k naturalnego), bo 7² ≡₄ 1, czyli 7⁷ ≡₄ 7. To daje [tex]7^{7^7}[/tex] = 7^4k+3 = [tex](7^4)^k[/tex]·7³ ≡₁₀ 1·343 ≡₁₀ 3.

Zadanie 4. Pokaż, że równanie x² – 5y² = 2 nie ma rozwiązań w liczbach naturalnych.
Rozwiązanie: Będziemy rozważać reszty z dzielenia przez 5. Zauważmy, że -5y² nie ma na nią wpływu, potrzebujemy zatem znaleźć liczbę, której kwadrat przystaje do 2 modulo 5. Rozumowanie analogiczne jak w zad. 2. prowadzi do wniosku, że takiej liczby nie ma.

Zadanie 5. Pokaż, że równanie 2^k = 9^k+1 nie ma rozwiązań w liczbach naturalnych.
Rozwiązanie. Będziemy rozważać reszty modulo 7. Ponieważ 2 przystaje do 9 modulo 7, to 2^k przystaje do 9^k, zatem nie przystaje do 9^k+1.

Zadanie 6. Znajdź sumę cyfr sumy cyfr sumy cyfr liczby 4444⁴⁴⁴⁴.
Rozwiązanie: Liczba z zadania nie będzie mieć więcej cyfr niż liczba 10000⁴⁴⁴⁴ = 17777 = 4444·4+1, a suma cyfr tej ostatniej to co najwyżej 9·17777, czyli nieco mniej niż 160000. Największa możliwa suma cyfr dla liczb mniejszych od 160000 jest osiągana dla liczby 99999 i wynosi 45, czyli szukamy sumy cyfr pewnej liczby nieprzekraczającej 45. Wśród takich liczb największą możliwą sumę cyfr ma 39 i wynosi ona 12. Szukana liczba znajduje się więc pomiędzy 1 a 12 włącznie. Aby ustalić, która z nich jest tą poszukiwaną, rozpatrzymy reszty modulo 9. Liczba 4444 przystaje modulo 9 do 7, więc 4444³ przystaje modulo 9 do 7³=343, ale 343 ≡₉ 1. Zatem do jedynki przystaje także 4444^3·1481 = 4444⁴⁴⁴³. Po pomnożeniu obu stron kongruencji 4444⁴⁴⁴³≡₉ 1 przez 4444 okazuje się, że 4444⁴⁴⁴⁴ przystaje modulo 9 do 4444, więc także do 7. Z uogólnionej cechy podzielności przez 9 wiemy, że operacja sumowania cyfr danej liczby nie zmienia reszty z dzielenia tej liczby przez 9, zatem szukaną liczbą jest 7.

Ostatnie zadanie pojawiło się na Międzynarodowej Olimpiadzie Matematycznej. Pokazuje to, że kongruencje stanowią naprawdę potężne narzędzie do rozwiązywania zadań.

A teraz spróbuj sam(a):

Zadanie 7. Pokaż, że równanie m³–n³ = 2022 nie ma rozwiązań w liczbach naturalnych.

Zadanie 8.  Znajdź resztę z dzielenia liczby 17³⁴² przez 5.

Zadanie 9. Wyznacz wszystkie takie dodatnie liczby naturalne n, dla których obie liczby: n²+n+1 oraz n²+n+3 są pierwsze. 

Zadanie 10.  Pokaż, że równanie k³ = 2ⁿ+15 nie ma rozwiązań w liczbach naturalnych.