IX OM - III - Zadanie 1

Zawody matematyczne:

IX OM, 1957-1958

Etap:

III

Dowieść, że iloczyn trzech kolejnych liczb naturalnych, z których środkowa jest sześcianem liczby naturalnej, jest podzielny przez $504$ .

Rozwiązanie

Mamy dowieść, że jeżeli $a$ jest liczbą naturalną większą od $1$ , to liczba

$ N = (a^3 - 1)a^3 (a^3 + 1) $

jest podzielna przez $504 = 7 \cdot 8 \cdot 9$ . Ponieważ liczby $7$ , $8$ , $9$ są pierwsze względem siebie, więc zadanie sprowadza się do wykazania podzielności $N$ przez każdą z tych liczb.

a) Liczbę $a$ możemy przedstawić w postaci $a = 7k + r$ , gdzie $k$ jest liczbą naturalną, a $r$ - jedną z liczb $0$ , $1$ , $2$ , $3$ , $4$ , $5$ , $6$ . Wówczas $a^3 = 7^3k^3 + 3 \cdot 7^2k^2r + 3 \cdot 7 kr^2 + r^3$ , zatem przy dzieleniu przez $7$ liczba $a^3$ daje taką samą resztę jak $r^3$ . Lecz $r^3$ jest jedną z liczb $0$ , $1$ , $8$ , $27$ , $64$ , $125$ , $216$ , zatem reszta z dzielenia $a^3$ przez $7$ jest jedną z liczb $0$ , $1$ , $6$ , co oznacza, że jedna z liczb $a^3$ , $a^3 - 1$ , $a^3 + 1$ jest podzielna przez $7$ .

b) Aby stwierdzić podzielność liczby $N$ przez $8$ , wystarczy zauważyć, że gdy $a$ jest liczbą parzystą, to $a^3$ jest podzielne przez $8$ , gdy zaś $a$ jest nieparzyste to $a^3 - 1$ i $a^3 + 1$ są dwiema kolejnymi liczbami parzystymi, jedna z nich jest więc podzielna przez $4$ , a ich iloczyn przez $8$ .

c) Liczbę $a$ możemy przedstawić w postaci $a = 3l + s$ , gdzie $l$ jest liczbą naturalną, a $s$ - jedną z liczb $0$ , $1$ , $2$ . Wówczas $a^3 = 3^3l^3 + 3 \cdot 3l^2s + 3 \cdot 3l \cdot s^2 + s^3$ , skąd widzimy, że $a^3$ daje przy dzieleniu przez $9$ resztę $s^3$ , tzn. $0$ , $1$ lub $8$ . W takim razie jedna z liczb $a^3$ , $a^3 - 1$ lub $a^3 + 1$ jest podzielna przez $9$ .

Uwaga 1. Łatwo spostrzec, że w tekście twierdzenia można mówić ogólniej o liczbach całkowitych zamiast o liczbach naturalnych.

Uwaga 2. Posługując się prostymi wiadomościami z teorii liczb, można rozumowania przeprowadzone wyżej w p. a) i c) zastąpić prostszymi. Według małego twierdzenia Fermata (Patrz Siódma Olimpiada Matematyczna, Warszawa 1957, zadanie nr 2), gdy liczba całkowita $a$ jest niepodzielna przez $7$ , to zachodzi kongruencja

$ a^6 \equiv 1 \pmod 7,\textrm{ czyli }(a^3 - 1) (a^3 + 1) \equiv 0 \pmod 7, $

skąd wynika, że

$ a^3 - 1 \equiv 0 \pmod 7 \textrm{ lub } a^3 + 1 \equiv 0 \pmod 7. $

Początkowe wiadomości o kongruencjach można znaleźć w książce Zadania z Olimpiad Matematycznych, Warszawa 1956, PZWS, s. 28.

Zatem gdy $a$ jest dowolną liczbą całkowitą, to jedna z liczb $a^3$ , $a^3 - 1$ , $a^3 + 1$ jest podzielna przez $7$ .

Gdy chodzi o podzielność przez $9$ , które nie jest liczbą pierwszą, trzeba zastosować twierdzenie ogólniejsze od twierdzenia Fermata, a mianowicie tzw. twierdzenie Eulera (sławny matematyk szwajcarski, 1707-1783). Niech $m$ będzie liczbą naturalną, a $\varphi(m)$ niech oznacza ilość liczb naturalnych nie większych od $m$ i pierwszych względem $m$ . Na przykład $\varphi(1) = \varphi(2) = 1$ , $\varphi(3) = \varphi(4) = 2$ , $\varphi(5) = 4$ , $\varphi(6) = 2$ , $\varphi(7) = 6$ , $\varphi(8) = 4$ , $\varphi(9) = 6$ itd.

Twierdzenie Eulera brzmi: Jeżeli liczby całkowite $a$ i $m > 1$ są pierwsze względem siebie, to

$ a^{\varphi(m)} \equiv 1 \pmod m. $

Gdy na przykład $m = 9$ , otrzymujemy twierdzenie: jeżeli liczba całkowita $a$ nie jest podzielna przez $3$ , to

$ a^6 \equiv 1 \pmod 9, $

skąd - jak wyżej - wynika, że przy dowolnym całkowitym $a$ jedna z liczb $a^3$ , $a^3 - 1$ , $a^3 + 1$ jest podzielna przez $9$ .

Dowód twierdzenia Eulera można przeprowadzić, jak następuje. Niech $r_1, r_2, \ldots, r_\varphi$ , gdzie $\varphi = \varphi(m)$ , będzie ciągiem rosnącym wszystkich liczb naturalnych nie większych od $m$ i pierwszych względem $m$ . Wówczas każda z liczb $ar_1, ar_2, \ldots, ar_\varphi$ jest także pierwsza względem $m$ ; niech $\rho_1, \rho_2, \ldots, \rho_\varphi$ oznaczają reszty tych liczb z dzielenia przez $m$ , wobec czego

$ (1) \qquad \alpha r_1 \equiv \rho_1 \pmod m,\ \alpha r_2 \equiv \rho_2 \pmod m,\ \ldots, \alpha r_\varphi \equiv \rho_\varphi \pmod m. $

Każda z liczb $\rho_i$ jest pierwsza względem $m$ , gdyż według (1) $\alpha r_i - \varphi_i$ jest podzielne przez $m$ , a $\alpha r_i$ jest pierwsze względem $m$ . Ponadto liczby $\rho_i$ są wszystkie różne, albowiem z równości $\rho_i = \rho_k$ wynikałoby, że $\alpha r_i \equiv \alpha r_k \pmod m$ , więc też $r_i \equiv r_k \pmod m$ , czyli $r_i \equiv r_k$ wbrew definicji liczb $r_i$ . Zatem liczby $\rho_1, \rho_2, \ldots, \rho_\varphi$ różnią się od liczb $r_1, r_2, \ldots, r_\varphi$ co najwyżej porządkiem i zachodzi równość