IV OM - I - Zadanie 4

Dowieść, że liczba $ 2^{55} + 1 $ jest podzielna przez $ 11 $.

Rozwiązanie

Wiadomo, że jeśli $ n $ jest liczbą naturalną, a $ a $ i $ b $ są liczbami dowolnymi, to

\[<br />
a^n - b^n = (a-b) (a^{n-1} + a^{n-2}b + a^{n-3}b^2 + \ldots + ab^{n-2} + b^{n-1}).<br />
\]

Podstawiając w tej równości $ a = 2^5 $, $ b = - 1 $, $ n = 11 $, otrzymujemy

\[<br />
2^{55} + 1 = (2^5 + 1) (2^{50} - 2^{45} + 2^{40} - \ldots - 2^5 + 1) = 33 \cdot C,<br />
\]

gdzie $ C $ jest liczbą całkowitą. Liczba $ 2^{55} + 1 $ jest więc podzielna przez $ 33 $, a tym samym i przez $ 11 $.

Uwaga 1. W taki sam sposób możemy dowieść ogólnie, że liczba $ 2^{5n} + 1 $, gdzie $ n $ oznacza dowolną liczbę nieparzystą, jest podzielna przez $ 11 $.

Uwaga 2. Zadanie powyższe, jak również wiele innych zadań dotyczących podzielności liczb, można szybko rozwiązać posługując się pojęciem i własnościami {\it kongruencyj}.

0 dwóch liczbach całkowitych, $ a $ i $ b $ mówimy, że są {\it w kongruencji} według modułu $ k $ lub że {\it przystają}, według modułu $ k $, jeżeli różnica $ a - b $ jest podzielna przez $ k $; zapisujemy to w postaci wzoru

\[<br />
a \equiv b \pmod k,<br />
\]

który nazywamy kongruencją.

Można również powiedzieć, że dwie liczby są w kongruencji według modułu $ k $, jeżeli dają tę samą resztę w dzieleniu przez $ k $.

Z definicji kongruencji możemy natychmiast wysnuć następujące wnioski:

$ a \equiv a \pmod k $ dla dowolnego całkowitego $ a $ i naturalnego $ k $.

2° Jeżeli $ a \equiv b \pmod k $, to $ b \equiv a \pmod k $

3° Jeżeli $ a \equiv b \pmod k $ i $ b \equiv c \pmod k $, to $ a \equiv c \pmod k $

4° Jeżeli $ a \equiv b \pmod k $ i $ c \equiv d \pmod k $, to $ a+c \equiv b+d \pmod k $.

Dowody twierdzeń 1 - 4 nie nastręczają najmniejszych trudności; niech czytelnik sam je przeprowadzi.

5° Jeżeli $ a \equiv b \pmod k $ i $ c \equiv d \pmod k $, to $ ac \equiv bd \pmod k $.

Dla dowodu wystarczy zauważyć, że $ ac - bd = ac - bc + bc - bd = (a - b) c + (c - d) b $.

Z twierdzenia 5° wynika twierdzenie:

6° Jeżeli $ a \equiv b \pmod k $, to $ a^2 \equiv b^2 \pmod k $, i ogólnie: $ a^n \equiv 6^n \pmod k $ dla dowolnego naturalnego $ n $. Ostatni wniosek wysnujemy przez indukcję zupełną.

Korzystając z kongruencyj rozwiążemy powyższe zadanie nr 18 w następujący prosty sposób:

Ponieważ $ 2^5 \equiv - 1 \pmod {11} $, więc $ (2^5)^{11} = (- 1)^{11} \pmod {11} $, skąd $ (2^5)^{11} = - 1 \pmod {11} $, a to znaczy, że $ 2^{55} + 1 $ jest podzielne przez $ 11 $.

Jako przykład zastosowania kongrueneyj rozwiążemy jeszcze zadanie:

Znaleźć ostatnią cyfrę liczby $ 2^{1000} $.

Ponieważ $ 2^5 \equiv 2 \pmod {10} $, więc

\[<br />
2^{1000} \equiv 2^{200} \equiv 2^{40} \equiv 2^8 \equiv 2^5 \cdot 2^3 \equiv 2 \cdot 2^3 \equiv 6 \pmod {10}.<br />
\]

Ostatnią cyfrą liczby $ 2^{1000} $ jest zatem $ 6 $.

Wykład teorii kongrueneyj oraz wiele zadań można znaleźć w książce: W. Sierpiński Teoria liczb, Warszawa-Wrocław 1950.

Komentarze

Dodaj nową odpowiedź