Kongruencje, czyli czasami lepiej wiedzieć mniej

Data ostatniej modyfikacji:
2022-01-12
Autor: 
Dawid Migacz
student matematyki na UWr
Dział matematyki: 
teoria liczb
Poziom edukacyjny: 
szkoła podstawowa
szkoła średnia z maturą
szkoła profilowana zawodowa

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 an 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. 
an b to kongruencja liczb a i b modulo n. Jeżeli an b oraz cn d, to także:

  • a+cn b+d
  • acn bd
  • akn bk 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 72022  przez 6.
Rozwiązanie. 7 ≡6 1, więc 720226 12022 = 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 n2 przystaje modulo 3 do 0, 1 lub 4. Ale 4 ≡3 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 7210 -1, a 7310 -7 ≡10 3. Po drugie 74 = 72·7210 (-1)(-1) = 1. Widzimy, że wielokrotności czwórki w wykładniku nie mają wpływu na ostateczny wynik. Następnie zauważamy, że 77 = 4k+3 (dla pewnego k naturalnego), bo 724 1, czyli 774 7. To daje [tex]7^{7^7}[/tex] = 74k+3 = [tex](7^4)^k[/tex]·7310 1·343 ≡10 3.

Zadanie 4. Pokaż, że równanie x2 – 5y2 = 2 nie ma rozwiązań w liczbach naturalnych.
Rozwiązanie: Będziemy rozważać reszty z dzielenia przez 5. Zauważmy, że -5y2 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 2k = 9k+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 2k przystaje do 9k, zatem nie przystaje do 9k+1.

Zadanie 6. Znajdź sumę cyfr sumy cyfr sumy cyfr liczby 44444444.
Rozwiązanie: Liczba z zadania nie będzie mieć więcej cyfr niż liczba 100004444 = 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 44443 przystaje modulo 9 do 73=343, ale 343 ≡9 1. Zatem do jedynki przystaje także 44443·1481 = 44444443. Po pomnożeniu obu stron kongruencji 444444439 1 przez 4444 okazuje się, że 44444444 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 m3n3 = 2022 nie ma rozwiązań w liczbach naturalnych.

Zadanie 8.  Znajdź resztę z dzielenia liczby 17342 przez 5.

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

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

 

Powrót na górę strony