Olimpiady Matematyczne

Matematyka jest drzwiami i kluczem do nauki.

Roger Bacon

Komentarz

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

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

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

$ 2^{55} + 1 = (2^5 + 1) (2^{50} - 2^{45} + 2^{40} - \ldots - 2^5 + 1) = 33 \cdot C, $

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

$ a \equiv b \pmod k, $

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:

1° $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$ .