Gdy w szkole poznajemy cechy podzielności liczb, to dowiadujemy się jak sprawdzić, że dana liczba całkowita jest podzielna np. przez 3, 4 czy 9. Ale skąd się te cechy podzielności biorą? I jak w łatwy sposób znajdować nowe?
Wbrew pozorom dowody cech podzielności oraz znajdywanie nowych jest dosyć łatwe. W tym wpisie przedstawimy dwie idee pozwalające to czynić. Jedna z nich pozwoli znajdować te cechy podzielności, które znamy ze szkoły. Z kolei dzięki drugiej znajdziemy cechy nieco innego rodzaju, o których w szkole się raczej nie uczy.
Zacznijmy jednak od pewnej oczywistej acz szalenie istotnej obserwacji. Każdą liczbę naturalną \(n\) jesteśmy w stanie przedstawić w postaci \[x=10^ka_k+10^{k-1}a_{k-1}+\cdots +10a_1+a_0,\] gdzie \(1\leqslant a_k\leqslant 9\), to kolejne cyfry przedstawienia liczby \(x\) w systemie dziesiętnym. Np. \[1234=1\cdot 10^3+2\cdot 10^2+3\cdot 10^1+4\cdot 10^0.\]
Inną prostą lecz szalenie istotną rzeczą są podstawowe własności dzielenia z resztą. Jeżeli \[x=a+b\] oraz liczba \(b\) daje taką samą resztę z dzielenia przez \(n\) jak liczba \(c\), to liczby \(a+b\) oraz \(a+c\) dają takie same reszty przy dzieleniu przez \(n\). Zamiast dwóch, możemy dodać więcej liczb. Więc liczba \(mb\) daje przy dzieleniu przez \(n\) taką samą resztę jak \(mc\) dla dowolnej liczby całkowitej \(m\). Z tego wynika, że jeżeli \(r_k\) daje taką samą resztę przy dzieleniu przez \(n\) co \(10^k\), to liczby \[10^ka_k+10^{k-1}a_{k-1}+\cdots +10a_1+a_0\] oraz \[r_ka_k+r_{k-1}a_{k-1}+\cdots +r_1a_1+r_0a_0\] również dają tę samą resztę przy dzieleniu przez \(n\). W szczególności, jednocześnie albo obie są podzielne przez \(n\) albo nie.
I w tej własności jest zawarta idea pozwalająca sformułować skrótowo bardzo (jeszcze) ogólną zasadę podzielności przez dowolną liczbę naturalną \(n\).
Liczba \(x\) jest podzielna przez \(n\) dokładnie wtedy, gdy podzielna jest suma \[r_ka_k+r_{k-1}a_{k-1}+\cdots +r_1a_1+r_0a_0.\]
Widzimy tutaj od razu podobieństwo do znanych cech podzielności np. przez 3 czy 9, gdzie po prostu dodajemy cyfry danej liczby (tzn. mnożymy każdą przez stosowne \(r_k=1\)). Z każdą liczbą \(n\) (podzielność przez którą badamy) możemy więc stowarzyszyć ciąg, którego elementy, aby uwypuklić liczbę \(n\), oznaczać będziemy \(r_k^n\).
Tak na marginesie fakt, że liczby całkowite \(a\) oraz \(b\) dają taką samą resztę przy dzieleniu przez \(n\) notujemy \[a\equiv b\pmod{n}\] i mówimy, że \(a\) oraz \(b\) przystają modulo n. Zaś samo powyższe wyrażenie nazywamy kongruencją. Równoważnie przystawanie modulo \(n\) oznacza, że różnica \(a-b\) jest podzielna przez \(n\). Wspomniane wcześniej własności mówią po prostu, że kongruencje można dodawać stronami oraz mnożyć przez liczbę całkowitą. Tzn. jeżeli \[a\equiv b\pmod{n}\] oraz \[c\equiv d\pmod{n},\] to \[a+c\equiv b+d\pmod{n}.\] Z tego wprost wynika, że również \[ma\equiv mb\pmod{n}\] dla liczby całkowitej \(m\).
Tak na marginesie, symbol kongruencji \(\equiv\) został wprowadzony przez samego Karola Fryderyka Gaussa w jego słynnym dziele Disquisitiones Arithmeticae, które zostało wydane, gdy miał jedynie 24 lata.
Warto również dodać, że jeżeli do liczb \(r_k^n\) dodamy lub odejmiemy wielokrotności \(n\) (niekoniecznie te same), to otrzymamy nowy ciąg \(\tilde{r}_k^n\). Mimo to liczba \(x\) dalej będzie podzielna przez \(n\) dokładnie wtedy, gdy suma liczb \(\tilde{r}_k^na_k\).
Spróbujmy teraz wykorzystać wspomnianą pierwszą ideę, aby udowodnić na początek (bardzo prostą) cechę podzielności przez 2 oraz uogólnić poczynione przy tym obserwacje próbując znaleźć analogiczne cechy dla innych liczb. Wiemy doskonale ze szkoły, że liczba \(x\) jest podzielna przez 2 jeżeli jej cyfra jedności jest podzielna przez 2, tj. ostatnią jej cyfrą jest 0, 2, 4, 6 lub 8. Dowód jest bardzo prosty choć niektórym może się wydawać nieco rozbudowany. Pozwoli on nam jednak znaleźć cechy podzielności dla wielu innych liczb.
Liczba \(10^m\) jest podzielna przez 2 dla każdego \(m\geqslant 1\), a więc i liczby postaci \(10^ma_m\) są dla \(m\geqslant 1\) przez 2 podzielne bez względu na to ile dokładnie jest równe \(a_m\). Tzn. \[r_m^2=\left\{\begin{array}{ll}1 & \textrm{ dla } m=0\\ 0 &\textrm{ dla } m\geqslant 1\end{array}\right.\] Wobec tego jedynie liczby typu \(10^0a_0=a_0\) mogą nie być podzielne przez 2. A ponieważ każdą liczbę naturalną można przedstawić w postaci \[x=10^ka_k+10^{k-1}a_{k-1}+\cdots +10a_1+a_0,\] to możemy odrzucić część \[10^ka_k+10^{k-1}a_{k-1}+\cdots +10a_1,\] bo jest ona zawsze podzielna przez 2, zostawiając jedynie \(a_0\). Zatem liczba \(x\) jest podzielna przez 2 dokładnie wtedy, gdy jej cyfra jedności jest podzielna przez 2 czyli gdy jest nią 0, 2, 4, 6 lub 8.
Zauważmy, że 2 nie jest jedyną liczbą o własności, że \(2|10^m\) dla \(m\geqslant 1\) (tj. \(10^m\) jest podzielne przez 2). Analogiczną własność ma 5 oraz 10. Wobec tego liczba całkowita \(x\) jest podzielna przez 5 dokładnie wtedy gdy jej cyfra jedności jest, czyli gdy cyfrą jedności \(x\) jest 0 lub 5. Z analogicznych powodów liczba \(x\) jest podzielna przez 10 tylko gdy jej cyfrą jedności jest 0.
Liczby 2, 5 oraz 10 mają siostrzaną cechę podzielności bo \(10=2\cdot 5\) czyli poza \(k=0\) każda liczba \(10^k\) daje resztę 0 przy dzieleniu przez każdą z tych liczb. Czyżbyśmy więc właśnie znaleźli sposób na znajdywanie niektórych prostych cech podzielności w systemach liczbowych opartych na innych liczbach złożonych niż 10? 😉 Ale wróćmy do systemu dziesiętnego.
W przypadku liczb \(n=2, 5, 10\) mieliśmy sytuację, w której reszty z dzielenia liczb \(10^m\) przez \(n\) były równe 0 począwszy od \(m=1\). Ponieważ \(10=2\cdot 5\), to są to jedyne liczby całkowite dodatnie o tej własności. A co dla liczb \(n\), dla których owe reszty są zerowe począwszy od pewnego \(m\gt 1\)? W takim przypadku badając podzielność przez \(n\) możemy odrzucić część \[10^ka_k+10^{k-1}a_{k-1}+\cdots +10^{m+1}a_{m+1}\] i skupić się jedynie na \[10^ma_m+10^{m-1}a_{m-1}+\cdots +10a_1,\] tzn. liczba \(x\) jest podzielna przez \(n\) dokładnie wtedy, gdy liczba utworzona (z zachowaniem kolejności) z jej ostatnich \(m\) cyfr jest podzielna przez \(n\). Jeżeli \(x\) ma mniej niż \(m\) cyfr, to bierzemy pod uwagę jej wszystkie cyfry.
Przykładem takiej liczby jest 4. Reszta z dzielenia \(10^0\) przez 4 jest równa 1, zaś dla \(10^1\) jest równa 2, a dla \(k\geqslant 2\) jest równa 0. Z tego wynika znana cecha podzielności przez 4, że liczba \(n\) jest podzielna przez 4 dokładnie wtedy, gdy liczba powstała z jej dwu ostatnich cyfr, tj. \[a_0+10\cdot a_1\] jest podzielna przez 4. Możemy ją jeszcze ciut ulepszyć.
Ponieważ \[10\equiv 2\pmod{4},\] to \(x\) jest podzielna przez \(4\), gdy \(2a_1+a_0\) jest. A jeżeli od 2 odejmiemy 4, to otrzymamy -2 więc również \[10\equiv -2\pmod{4},\] a stąd od razu dostajemy, że \(2a_1+a_0\) możemy zastąpić przez \(-2a_1+a_0\).
Ogólniej, ponieważ \(10=2\cdot 5\), to \(10^m\) jest zawsze podzielna przez \(2^a\cdot 5^b\), o ile \(m\geqslant\max\{a,b\}\). Zatem liczba \(x\) jest podzielna przez \(n=2^a\cdot 2^b\) dokładnie wtedy, gdy podzielna przez \(n\) jest liczba utworzona z jej ostatnich \(\max\{a,b\}\) cyfr (z zachowaniem ich porządku). W szczególności liczba \(x\) jest podzielna przez \(50=2^1\cdot 5^2\) wtedy, gdy liczba utworzona z jej dwu ostatnich cyfr jest. Zaś liczba \(x\) jest podzielna przez \(2^n\) dokładnie, gdy liczba utworzona z jej ostatnich \(n\) jest.
Idźmy dalej. Łatwo sprawdzić, że liczba \(10^m\) daje resztę 1 przy dzieleniu zarówno przez 3 jak i przez 9 dla każdego \(m\geqslant 0\), tzn. wszystkie \(r_m^3, r_m^9\) są jedynkami. Dlatego liczba \[x=10^ka_k+10^{k-1}a_{k-1}+\cdots +10a_1+10^0a_0\] jest podzielna przez 3 dokładnie wtedy, gdy przez 3 podzielna jest liczba \[1\cdot a_k+1\cdot a_{k-1}+\cdots +1\cdot a_1+1\cdot a_0\] czyli suma jej cyfr. Z tych samych powodów liczba \(x\) jest podzielna przez 9 dokładnie wtedy, gdy suma jej cyfr.
Ciągi \(r_k^n\) mają wspólną cechę, którą dało się już dostrzec, choć być może niezbyt wyraźnie. Mianowicie, ciąg \(r_k^n\) jest dla każdej liczby naturalnej \(n\) okresowy od pewnego momentu. Nietrudno się o tym przekonać. Gdy badamy podzielność przez \(n\), to reszta z dzielenia przez \(n\) jest zawsze mniejsza od \(n\). Innymi słowy, ciąg \(\{r_j^n\}\) jest nieskończonym ciągiem mającym skończenie wiele różnych wyrazów. Stąd, dla pewnych \(j\lt m\) reszta z dzielenia liczb \(10^j\) oraz \(10^m\) musi być taka sama, tj. \(r_j^n=r_m^n\). Liczby \(10^{j+1}\) oraz \(10^{m+1}\) dają więc taką samą resztę przy dzieleniu przez \(n\), co \(10r_j^n\). Z tego wynika, że również \(r_{j+1}^n=r_{m+1}^n\).
Wiemy, że liczba jest podzielna przez 6 dokładnie gdy jest podzielna przez 2 oraz 3. Ponieważ \(10^m\) daje resztę 4 przy dzieleniu przez 6 dla \(m\geqslant 1\), to liczba \[x=10^ka_k+10^{k-1}a_{k-1}+\cdots +10a_1+a_0\] jest podzielna przez 6 dokładnie wtedy, gdy przez 6 jest podzielna liczba \[4\cdot a_k+4\cdot a_{k-1}+\cdots +4\cdot a_1+a_0.\] Zgodzimy się chyba, że pierwsza cecha podzielności wydaje się przystępniejsza.
Kolejne elementy ciągu \(r_j^{11}\), to \(1,10,1,10,\ldots\). Zatem liczba \[x=10^ka_k+10^{k-1}a_{k-1}+\cdots +10a_1+10^0a_0\] jest podzielna przez 11 dokładnie wtedy, gdy podzielna jest suma \[a_0+10a_1+a_2+10a_3+\cdots\] Ponieważ \[10\equiv 10\pmod{11},\] to odejmując 11 od jednej dziesiątki mamy również \[10\equiv -1\pmod{11}.\] Z tego wynika, że liczba \(x\) jest podzielna przez 11 dokładnie wtedy, gdy suma \[a_0-a_1+a_2-a_3+\cdots.\] Czyli od sumy cyfr na miejscach nieparzystych odejmujemy sumę tych na miejscach parzystych.
Przy dzieleniu liczb \(10^j\) przez 7 otrzymujemy powtarzający się ciąg reszt 1, 3, 2, 6, 4, 5. Ponieważ \[6\equiv -1\pmod{7},\ 4\equiv -3\pmod{7}\textrm{ oraz }5\equiv -2\pmod{7},\] to możemy go zastąpić ciągiem 1, 3, 2, -1, -3, -2. Przykładowo liczba 1224825 jest podzielna przez 7 bo podzielna przez 7 jest liczba \[1\cdot 5+3\cdot 2+2\cdot 8-1\cdot 4-3\cdot 2-2\cdot 1+1\cdot 1=14.\] Dla liczby 13 stosowny ciąg to 1, 10, 9, 12, 3, 4. Możemy go zastąpić ciągiem 1, -3, -4, -1, 3, 4
Dla liczb 7 oraz 13 (jak i naturalnie innych) możemy stworzyć inne cechy podzielności. Zauważmy, że \[1000\equiv -1\pmod{7}\textrm{ oraz }1000\equiv -1\pmod{13}.\] Z tego wynika, że dla dowolnego \(k\geqslant 0\) zachodzi \[1000^k\equiv (-1)^k\pmod{7}\textrm{ oraz }1000^k\equiv (-1)^k\pmod{13}.\] Wobec tego aby badać podzielność liczby \(x\) przez 7 oraz 13 wystarczy badać naprzemienne sumy liczb utworzonych z bloków składających się po 3 cyfry. Przykładowo dla liczby 1221033 mamy \[033-221+001=189=27\cdot 7.\]
Mamy więc pewną modyfikację naszej idei. Zamiast badać reszty z dzielenia liczb postaci \(10^k\) przez \(n\) badamy reszty z dzielenia przez \(n\) liczb postaci \(100^k\), \(1000^k\) itd. Wtedy zamiast mnożyć przez stosowne reszty kolejne cyfry, mnożymy liczby powstałe z odpowiednich bloków cyfr stosownej długości. Prześledźmy to na jeszcze kilku przykładach.
Ponieważ \[100\equiv 1\pmod{33},\] a więc również \[100^k\equiv 1^k\pmod{33},\] to liczba jest podzielna przez 33 dokładnie wtedy, gdy podzielna jest stosowna suma liczb utworzonych z dwucyfrowych bloków, tzn. np. 7524 jest podzielna przez 33, bo podzielna jest liczba 75+24=99. Z kolei z tego, że
\[1000\equiv 1\pmod{27}\textrm{ oraz }1000\equiv 1\pmod{37}\] wynikają stosowne cechy podzielności przez 27 oraz 37. Np. 45843 jest podzielna przez 37 bo \(843+45=888=37\cdot 24\).
Teraz omówimy cechy podzielności innego rodzaju oraz metodę pozwalającą łatwo je znajdywać. Sposób ten działa jedynie gdy badamy podzielność przez liczby względnie pierwsze z 10, tj. zakończone na 1, 3, 7 lub 9. Zacznijmy od przykładu z cechą podzielności przez 7. Przedstawmy liczbę \(x\) jako sumę cyfry jedności oraz całej reszty, tj. w postaci \[x=10a+b,\] gdzie \(b\) jest cyfrą jedności. W dalszej części cały czas zakładamy, że liczbę \(x\) przedstawiamy w takiej właśnie postaci. Okazuje się, że \(x\) jest podzielna przez 7 dokładnie wtedy, gdy przez 7 podzielna jest liczba \(a-2b\). Przykładowo dla x=49 mamy 4-18=-14, która jest podzielna przez 7, a więc i 49 jest. Jest to cecha nieco innego rodzaju niż dotychczas poznane.
Aby móc przedstawić ogólny sposób znajdywania cech tego rodzaju, zacznijmy od prostego i znanego lematu.
Lemat
Dla dowolnych dodatnich liczb całkowitych \(a, b\) takich, że \((a,b)=1\) (tj. względnie pierwszych) istnieją liczby całkowite \(r, s\) takie, że \[ar+bs=1.\]
Załóżmy, że chcemy znaleźć cechę podzielności przez liczbę \(n\) względnie pierwszą z \(10\). Znajdujemy wpierw takie liczby całkowite \(r,s\), że \[nr+10s=1.\] Na mocy przytoczonego wyżej lematu wiemy, że takie liczby zawsze istnieją. Okazuje się wówczas, że
Twierdzenie (Koether)
Liczba \(x=10a+b\) jest podzielna przez \(n\) wtedy i tylko wtedy, gdy przez \(n\) podzielna jest liczba \[a+bs.\]
Dowód przedstawimy na końcu, najpierw jakiś przykład. Ponieważ \[13\cdot (-3)+4\cdot 10=1,\] to aby sprawdzić czy liczba \(x\), np. \(3302=10\cdot 330+2\), jest podzielna przez 13 badamy podzielność przez 13 sumy \[330+2\cdot 4=338=10\cdot 33+8.\] Dalej mamy \(33+8\cdot 4=65\). A ponieważ 65 jest podzielne przez 13 to i 3302 jest.
Problematyczne może się wydawać znalezienie stosownych liczb \(r\) oraz \(s\). Lemat mówi, że takie liczby istnieją, lecz nie mówi jak je znaleźć. Jednak wbrew pozorom jest to bardzo proste. Jeżeli cyfrą jedności danej liczby \(x\) jest m, to \(x=10t+m\) dla pewnego \(t\). Jak znaleźć stosowne \(r\) oraz \(s\) dla danego \(t\) pokazuje poniższa tabelka. Warto nadmienić, że w ogólności, liczby \(r\) oraz \(s\) nie są wyznaczone jednoznacznie. Może istnieć wiele takich par dla konkretnego \(n\).
\(n\) | \(nr+10s=1\) | s |
\(10t+1\) | \((10t+1)\cdot 1+10\cdot (-t)\) | -t |
\(10t+3\) | \((10t+3)\cdot (-3)+10\cdot (3t+1)\) | 3t+1 |
\(10t+7\) | \((10t+7)\cdot 3+10\cdot (-3t-2)\) | -3t-2 |
\(10t+9\) | \((10t+9)\cdot (-1)+10\cdot (t+1)\) | t+1 |
Teraz przedstawimy dowód twierdzenia Koethera.
Załóżmy, że \(n|x\), tj. \(n|(10a+b)\). Istnieje więc liczba całkowita \(t\) taka, że \[nt=10a+b=10a+b(nr+10s)=10a+bnr+10bs.\] Stąd \[n(t-br)=10a+10bs=10(a+bs).\] Czyli \(n|10(a+bs)\). A ponieważ (n,10)=1, to \(n|(a+bs)\).
Teraz załóżmy, że \(n|(a+bs)\), istnieje wówczas takie \(k\in\mathbb Z\), że \(nk=a+bs\). Stąd \(10nk=10a+10bs\). Z tego mamy, że \[n(10k+br)=10a+10bs+nbr=10a+b(10s+nr)=10a+b=x\] i \(n|x\).
Literatura:
R.T. Koether, A General Test For Divisibility , Pi Mu Epsilon J., 5(8) (1973), s. 420-424.
W. Sierpiński, Teoria Liczb, PWN (1959).
.
Wytłumaczone znakomicie.
Zaczynam przegląd bloga, zapowiada się interesująco.