Krótkie wprowadzenie do arytmetyki modulo
Z zadaniami dotyczącymy podzielności spotykamy się w szkole średniej relatywnie często i mamy w pogotowiu kilka standardowych sposobów na ich rozwiązywanie - najczęściej wyłączanie dzielnika przed nawias i manipulacje algebraiczne. W niektórych jednak przypadkach prościej, a przede wszystkim bardziej elegancko jest wyrazić problem w języku arytmetyki modulo.
Rozważmy zadanie przedstawione obok. Zauważmy, że nie mamy tu do czynienia z problemem typu “wykaż, że (…) jest podzielne przez 9”, a raczej szukamy, w dodatku wszystkich, par wykładników spełniających założenie. Ponadto, nie mamy niestety żadnego “standardowego” wzoru na dodawanie potęg, w szczególności, gdy nie znamy żadnej zależności zachodzącej pomiędzy wykładnikami.
Przystawanie modulo n
Weźmy liczby naturalne (nietrudno natomiast podane dalej definicje i własności rozszerzyć na zbiór liczb całkowitych) a, b i n. O liczbach a i b powiemy, że są przystające modulo n, jeżeli dają te samą resztę z dzielenia przez n. Piszemy: a≡b (mod n).
Dla przykładu:
2≡5 (mod 3), bo zarówno z dzielenia 2 jak i 5 przez 3 otrzymujemy resztę 2.
11≡18 (mod 7), bo obie liczby przy dzieleniu przez 7 dają resztę 4.
0≡12 (mod 6), bo zarówno 0 jak i 12 są liczbami podzielnymi przez 6.
W szczególności, jeżeli liczba naturalna a jest podzielna przez n, to 0≡a (mod n).
Nietrudno przekonać się, że relacja przystawania modulo zachowuje się całkiem “porządnie” w obliczu podstawowych działań arytmetycznych - w szczególności przy dodawaniu i mnożeniu (z odejmowaniem również nie ma wielkiego problemu; przy dzieleniu, jak często, trzeba trochę więcej uważności).
Rozważmy liczby naturalne a, b, p, q, n takie, że
a≡p (mod n)
b≡q (mod n)
Zachodzi wtedy:
(a+b)≡(p+q) (mod n)
(ab)≡(pq) (mod n)
Obie równości łatwo uzasadnić standardowymi metodami - skoro a i p dają te same reszty z dzielenia, to dla pewnej liczby całkowitej k:
a=nk+p
Analogicznie, dla b, q i pewnej liczby całkowitej l:
b=nl+q
Stąd otrzymujemy:
a+b=nk+p+nl+q=n(k+l)+(p+q)
ab=(nk+p)(nl+q)=n(nkl+kq+lp)+(pq)
Rozwiązanie zadania
Wróćmy do naszego zadania. Zastanówmy się najpierw jakie reszty z dzielenia przez 9 dają kolejne potęgi liczby 2:
2^0=1≡1 (mod 9)
2^1=2≡2 (mod 9)
2^2=4≡4 (mod 9)
2^3=8≡8 (mod 9)
2^4=16≡7 (mod 9)
2^5=32≡5 (mod 9)
2^6=64≡1 (mod 9)
2^7=128≡2 (mod 9)
Na podstawie tego, co zauważyliśmy wcześniej na temat mnożenia, możemy się spodziewać, że cykl reszt: 1,2,4,8,7,5 będzie się stale powtarzał. W istocie, dla dowolnej liczby naturalnej k zachodzi:
2^(6k)≡1 (mod 9)
2^(6k+1)≡2 (mod 9)
2^(6k+2)≡4 (mod 9)
2^(6k+3)≡8 (mod 9)
2^(6k+4)≡7 (mod 9)
2^(6k+5)≡5 (mod 9)
Szukamy takich wykładników, które dadzą nam sumę 2^m + 2^n podzielną przez 9, a więc (2^m + 2^n)≡0 (mod 9). Wiemy natomiast, że zachodzi 0≡9 (mod 9) - możemy więc dążyć do sytuacji, w której (2^m + 2^n)≡9 (mod 9). Po lewej stronie przystawania modulo mamy dodawanie - skorzystajmy więc z tego, co wyżej powiedzieliśmy o dodawaniu modulo i zapiszmy 9 po prawej stronie również w postaci dodawania. Korzystając tylko z liczb występujących w naszym cyklu reszt możemy to zrobić na 3 sposoby (z dokładnością do kolejności składników):
9=1+8, co daje (2^m + 2^n)≡(1+8) (mod 9);
9=2+7, co daje (2^m + 2^n)≡(2+7) (mod 9);
9=4+5, co daje (2^m + 2^n)≡(4+5) (mod 9).
Rozważmy najpierw każdą z opcji z osobna:
(2^m + 2^n)≡(1+8) (mod 9)
Jesteśmy więc w sytuacji, gdzie 2^m≡1 (mod 9) i 2^n≡8 (mod 9). (Bądź odwrotnie, możemy m i n zamienić rolami, nie wpływa to jednak na rozwiązanie, jako że pełnią one symetryczne role). Wiemy natomiast, że aby potęga liczby 2 przystawała do 1 modulo 9, to wykładnik przy 2 musi być wielokrotnością 6. Podobnie, jeśli chcemy przystawania do 8 (mod 9) to potrzeba, żeby wykładnik przy 2 dawał przy dzieleniu przez 6 resztę 3. Ostatecznie, dla pewnych liczb naturalnych k,l musimy mieć:
m=6k
n=6l+3(2^m + 2^n)≡(2+7) (mod 9)
Wnioskując jak w sytuacji 1 musimy mieć:
m=6k+1
n=6l+4(2^m + 2^n)≡(4+5) (mod 9)
Wnioskując jak w sytuacji 1 musimy mieć:
m=6k+2
n=6l+5
Zbierając wszystkie wnioski razem otrzymujemy ostateczną odpowiedź:
Żeby 2^m+2^n było liczbą podzielną przez 9, m i n muszą być liczbami naturalnymi, które przy dzieleniu przez 6 dają reszty różniące się o 3.