IX OM - III - Zadanie 1

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

\[<br />
N = (a^3 - 1)a^3 (a^3 + 1)<br />
\]

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

\[<br />
a^6 \equiv 1 \pmod 7,\textrm{ czyli }(a^3 - 1) (a^3 + 1) \equiv 0 \pmod 7,<br />
\]

skąd wynika, że

\[<br />
a^3 - 1 \equiv 0 \pmod 7 \textrm{ lub } a^3 + 1 \equiv 0 \pmod 7.<br />
\]

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

\[<br />
a^{\varphi(m)} \equiv 1 \pmod m.<br />
\]

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

\[<br />
a^6 \equiv 1 \pmod 9,<br />
\]

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

\[<br />
(1) \qquad<br />
\alpha r_1 \equiv \rho_1 \pmod m,\<br />
\alpha r_2 \equiv \rho_2 \pmod m,\<br />
\ldots,<br />
\alpha r_\varphi \equiv \rho_\varphi \pmod m.<br />
\]

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ść

\[<br />
(2) \qquad<br />
r_1r_2\ldots r_\varphi =<br />
\rho_1\rho_2\ldots \rho_\varphi.<br />
\]

Mnożąc kongruencje (1) stronami, otrzymujemy

\[<br />
(3) \qquad a^\varphi \cdot r_1r_2\ldots r_\varphi = \rho_1\rho_2\ldots \rho_\varphi \pmod m.<br />
\]

Ponieważ każda z liczb $ r_i $ jest pierwsza względem $ m $, więc to samo dotyczy iloczynu tych liczb, wobec czego z (2) i (3) wynika, że

\[<br />
a^{\varphi(m)} \equiv 1 \pmod m,<br />
\]

czego należało dowieść.

Zauważmy, że gdy $ m $ jest liczbą pierwszą, to $ \varphi(m) = m - 1 $; twierdzenie Eulera daje w tym przypadku małe twierdzenie Fermata.

Komentarze

Dodaj nową odpowiedź