Nieznany aspekt znanego twierdzenia

Niemal wszyscy wiedzą, że liczba naturalna jest podzielna przez $9$ (odpowiednio przez $3$) wtedy i tylko wtedy, gdy suma jej cyfr jest podzielna przez $9$ (odpowiednio przez $3$). Ten prosty do sprawdzenia test podzielności można znacznie wzmocnić. W jaki sposób? Zapraszam do lektury.

Odsuńmy na bok dywagacje czym jest liczba, a czym cyfra. Matematycy lubują się w dzieleniu włosa na czworo i już po przeczytaniu pierwszego zdania artykułu sformułują co najmniej kilka uwag krytycznych (cyfra to znak graficzny służący do zapisu liczb, jaki system liczenia rozważam: czy dziesiątkowy, czy może dwójkowy, czy też szesnastkowy itd. itp.). Odnoszenie się do tego rodzaju uwag zupełnie nie wpływa na jasność wywodu, a jedynie odwraca uwagę Czytelnika od właściwej treści przekazu. Ale cóż… matematycy mają specyficzne cechy charakteru. Będąc matematykiem czasem mam je i ja. Ale przejdźmy do rzeczy.

Wspomniane na wstępie uogólnienie mało kto, gdyż rzadko jest ono nauczane w szkole. A szkoda. Poniżej zaprezentuję więc następujące twierdzenie.

Twierdzenie. Reszta z dzielenia dowolnej liczby naturalnej przez $9$ (odpowiednio przez $3$) jest taka sama, jak reszta z dzielenia sumy cyfr tej liczby przez $9$ (odpowiednio przez $3$).

Ze względu na popularyzatorski charakter mojego tekstu zdecydowałem się nie wchodzić w szczegóły dowodowe, a rozumowanie, które w dowodzie można zastosować, zilustruję na konkretnym przykładzie liczbowym.

Przykład. Wyznaczymy reszty z dzielenia liczby $5648$ przez $9$ oraz przez $3$.

W tym celu skorzystamy ze sposobu konstrukcji układu dziesiątkowego:\[5648=5\cdot 1000+6\cdot 100+4\cdot 10+8.\]Przyjrzyjmy się teraz następującemu rachunkowi:\begin{align*}
{\color{red}5648}&={\color{red}5}\cdot 1000+{\color{red}6}\cdot 100+{\color{red}4}\cdot 10+{\color{red}8}=\\
&={\color{red}5}\cdot (999+1)+{\color{red}6}\cdot (99+1)+{\color{red}4}\cdot (9+1)+{\color{red}8}=\\
&=({\color{red}5}\cdot 999+{\color{red}6}\cdot 99+{\color{red}4}\cdot 9)+({\color{red}5}+{\color{red}6}+{\color{red}4}+{\color{red}8})=\\
&=9\cdot({\color{red}5}\cdot 111+{\color{red}6}\cdot 11+{\color{red}4})+{\color{red}23}.
\end{align*}

Widzimy, że pierwszy składnik powyższej sumy jest podzielny przez $9$ (a więc i przez $3$), a suma cyfr liczby $5648$ wynosi $23$. Dlatego reszta z dzielenia liczby $5648$ przez $9$ (odpowiednio przez $3$) jest taka sama jak reszta z dzielenia sumy cyfr tej liczby (czyli $23$) przez $9$ (odpowiednio przez $3$). Szukane reszty wynoszą więc $5$ dla dzielenia przez $9$ oraz $2$ dla dzielenia przez $3$.

Powyższą metodę można zastosować w sytuacji ogólnej i ściśle udowodnić omawiane dziś twierdzenie. Pozostawiam to jako pożyteczne ćwiczenie dla zainteresowanych Czytelników.

Na koniec sprawdźmy czy obie reszty zostały poprawnie wyznaczone:

  • $5648-5=5643$, a suma cyfr tej liczby wynosi $18$, więc jest to liczba podzielna przez $9$,
  • $5648-2=5646$, a suma cyfr tej liczby wynosi $21$, więc jest to liczba podzielna przez $3$.

Tu znów okazja dla dociekliwego matematyka do wyrażenia krytyki: sprawdzam twierdzenie, które omawiam, za pomocą tego właśnie twierdzenia. Dla matematycznych purystów napiszę więc, że

  • $5648=9\cdot 627+5$,
  • $5648=3\cdot 1882+2$.

Jest bardzo wiele różnych cech podzielności, które warto zgłębić. Zapraszam do własnych poszukiwań.

PS. Warto kliknąć w obrazek znajdujący się w tekście artykułu.

6 komentarzy

  • Próbowałem niedawno wykombinować sprawną metodę sprawdzania pierwszości liczby z zakresu 1–300 w pamięci. Do tego potrzebujemy sprawdzać podzielność przez wszystkie pierwsze od 2 do 13 (przypadek szczególny 17×17=289 łatwo zapamiętać). Podzielność przez 7 i 11 jest jeszcze do ogarnięcia, ale czy jest jakaś w miarę szybka metoda sprawdzenia podzielności przez 13? Bo sposób opisany na Wiki, choć poprawny, jest jednak nieco za bardzo zagmatwany.

    • Zgodzę się, że jako metoda pamięciowa, ta cecha jest trudna do sprawdzenia – duże prawdopodobieństwo pomyłki. Myślę, że powodzenia upatrywałbym w metodzie brute force, czyli w szukaniu wielokrotności 13. O czym myślę? Powiedzmy, że mamy liczbę 289. Wiemy, że 260 jest podzielne przez 13, więc zostaje nam 29, czyli reszta wynosi 3. Szybko i sprawnie. Nieprawdaż? 🙂 No to jeszcze jedno: 187. Mamy 130, zostaje 57, a podzielne przez 13 jest 52, dlatego reszta wynosi 4. No to na koniec coś większego. Robię to bez wspomagaczy kalkulatorowych: 729. 520, zostaje 209. Dalej 130, zostaje 79, podzielne przez 13 jest 65, dalej 14 i reszta wynosi 1. 🙂 Jak dla mnie to działa sprawnie. W tej chwili zastanowiłem się czy nie skorzystać z sześcianu dziewiątki? Bezpośrednio się nie da. Ale mamy 81, co daje resztę 3, a 3×9=27 daje resztę 1. Też szybko. Ale tutaj nie ma co badać pierwszości. 🙂

      • Takiego właśnie brute force-a używam obecnie; metoda prosta i jak najbardziej poprawna, ale wymaga najpierw znalezienia wielokrotności „rozsądnie” blisko sprawdzanej liczby, potem odjęcia tego i owego raz, drugi a czasem i trzeci. A chciałoby się czegoś prostego, np. odjąć sumę cyfr na pozycjach parzystych od sumy cyfr na nieparzystych (jedenastka), albo „odciąć” ostatnią cyfrę, podwoić ją i odjąć od kawałka, który został przy odcinaniu po prawej stronie (siódemka) i tak dalej. Tymczasem dla trzynastki… No dobra. Chyba znalazłem. Podobnie jak dla siódemki, tylko zamiast mnożenia przez dwa mnożymy przez cztery, a zamiast odejmowania – dodajemy. Na przykład żeby sprawdzić czy 221 dzieli się przez 13, wykonujemy: 22+1×4=26. Dzieli się. Że też ja tego wcześniej nie znalazłem. 🙂

        • Ten algorytm działa tylko dla podzielności, reszty nim nie znajdziemy. Np. dla 222 mamy 22+2×4=30 i reszta wychodzi 4, a prawdziwą resztą jest 1. Dość prosto udowodnić to kryterium podzielności. Ale znów zostawmy dowód zainteresowanym. Swoją drogą ciekawe będzie znalezienie szybkiego algorytmu obliczającego resztę (robi to ten, który przedstawiłem w artykule). Byłby on bardziej elegancki. 🙂

          • No tak, ale mnie akurat reszty nie interesują w tym przypadku, tylko badanie pierwszości w głowie tj. bez kartki / komputera 🙂

          • Całkowicie rozumiem. Dziękuję za ciekawe pytanie inicjujące tę wymianę myśli. To pokazuje, że jednak warto pisać ten blog. Pozdrawiam bardzo serdecznie.

Napisz komentarz