Przez 7 i inne, czyli o cechowaniu podzielności

Mama posłała syna po ziemniaki, dając mu 10 złotych. Syn kupił 3 kilo i zwrócił mamie całą resztę, jaką otrzymał od sprzedawcy, czyli 3 złote i 30 groszy. Mama miała jednak wątpliwości, czy to była cała reszta. Dlaczego?

Takie zadanie mogłoby się znaleźć w podręczniku matematyki dla 5. klasy szkoły podstawowej w rozdziale dotyczącym cech podzielności. W rozwiązaniu wypadałoby dodać, że wątpliwości mamy okazały się nieuzasadnione, bo sprzedawca doliczył 10 groszy za reklamówkę.

Cecha podzielności przez 3 należy do najbardziej znanych. Jej dowód nie jest jednak tak trywialny, jak dwu innych, równie popularnych i praktycznych – przez 2 i przez 5. To, że liczby zakończone cyfrą parzystą dzielą się przez 2, a zakończone zerem lub piątką przez 5, jest dla każdego oczywiste. Natomiast nad tym, dlaczego suma cyfr liczby podzielnej przez 3 także dzieli się przez 3, warto się zastanowić, jeśli się tego nie wie.

Podstawą tej cechy jest następująca zależność: jeśli od liczby naturalnej n odejmiemy sumę jej cyfr S(n), to różnica zawsze będzie podzielna przez 9, a więc także przez 3, co zapisujemy w postaci: n–S(n) =r|3. A jeśli różnica dwóch liczb jest podzielna przez trzy, to albo obie te liczby nie są podzielne przez 3 (jak 10 zł i 6,70 zł w zadaniu o ziemniakach), albo obie są wielokrotnością 3. Ta druga możliwość wiąże się z cechą podzielności: jeśli liczba jest podzielna przez 3, to suma jej cyfr także. Bezpośrednio z opisanej zależności wynika oczywiście bliźniacza cecha podzielności przez 9: liczba jest podzielna przez 9, jeśli suma jej cyfr dzieli się przez 9.

Wypadałoby jeszcze udowodnić, że n–S(n)=r|9. W tym celu należy skorzystać z zapisu liczby w postaci sumy iloczynów jej s cyfr przez kolejne, malejące potęgi 10, zaczynając od a_s-1×10^s-1, a kończąc na a₀×10⁰. Na przykład, 312 865=3×10⁵+1×10⁴+2×10³+8×10²+6×10¹+5×10⁰.

Jak widać, każdy z tych iloczynów ma postać a_t×10^t, zaś odejmując od danej liczby sumę jej cyfr, zmniejszamy każdy iloczyn o a_t, czyli wszystkie przyjmują postać: a_t×10^t–a_t=a_t×(10^t–1). Wartość w nawiasie jest albo zerem (dla t=0), albo składa się z samych dziewiątek, czyli jest podzielna przez 9, a zatem suma takich wartości również jest wielokrotnością dziewięciu. Gdy n=312 865, to S(n) =25, które nie dzieli się przez 9, a skoro n–S(n) =r|9, więc n także nie jest wielokrotnością 9.

Znajomość prostych cech podzielności dla małych jednocyfrowych dzielników bywa przydatna w różnych sytuacjach, ale ogólnie temat trąci myszką, ponieważ znacznie łatwiej wykonać dzielenie, na przykład przez 19, używając kalkulatora, niż korzystając z cechy podzielności tej liczby, upewnić się, czy reszta z dzielenia jest zerem. Przed wiekami miało to sens, bo ręczne dzielenie wielocyfrowej liczby przez 19 jest dość żmudne, a przynajmniej czasochłonne, i może trafić się błąd. Niepraktyczność nie oznacza jednak, że zagadnienie nie jest interesujące, zwłaszcza że wiąże się z matematyką nie tylko rekreacyjną.

Bardzo łatwo dowieść cech podzielności przez 4 i przez 8. W pierwszym przypadku rozstrzygająca jest podzielność przez 4 dwucyfrowej końcówki, w drugim podzielność przez 8 końcówki trzycyfrowej. Wynika to z faktu, że po odjęciu (nie mylić z usunięciem) od liczby jej 2-cyfrowej końcówki pozostaje liczba będąca wielokrotnością 10², a więc podzielna przez 4, a po odjęciu końcówki 3-cyfrowej – zostaje wielokrotność 10³ podzielna przez 8. Równie łatwo wyjaśnić cechę podzielności przez 6 jako cechę podzielności przez 3 liczb parzystych. Z liczb jednocyfrowych pozostaje siódemka, której mogłoby dotyczyć następujące zadanie: w jaki najprostszy sposób, wykonując działania na cyfrach tworzących daną liczbę, sprawdzić, czy jest ona podzielna przez 7? Inaczej mówiąc: znajdź cechę podzielności przez 7.

W roku 1654 Blaise Pascal sformułował kryterium zwane czasem uniwersalną cechą podzielności. W rzeczywistości jest to uniwersalna metoda tworzenia cech podzielności, na której oparta jest większość najczęściej podawanych cech, dotyczących różnych dzielników. Jej istotę i skuteczność najlepiej przedstawić, gdy dzielnikiem (d) jest właśnie 7, ale przy okazji można „obsłużyć” kilka innych wartości d. Podstawę metody stanowi obliczenie reszt (r) z dzielenia 10^t (t=0, 1, 2, 3…) przez d. W tabeli znajdują się reszty r dla 0<t<9 i dla d równych 7, 8, 9, 11, 13 i 35.

Liczby w nawiasach są praktycznymi „zamiennikami” podanych obok – równymi im modulo d (mod d), ale mniejszymi co do wartości bezwzględnej, a więc wygodniejszymi przy wykonywaniu działań. Warto zauważyć, że ciąg kolejnych wartości r dla każdego d tworzy cykl, składający się co najwyżej z d–1 wyrazów (dla d=7) albo też jest lub staje się od pewnego wyrazu stały (dla d=8 i 9).

Skoro r_t=10^t mod d, to (a_t×10^t) mod d= (a_t×r_t) mod d. Jeśli po lewej stronie znaku równości pojawi się suma s iloczynów dla 0≤t≤s–1, to powstanie ogólny zapis liczby (s+1)-cyfrowej, a całość utworzy wzór określający kryterium Pascala:

(a_s×10^s+a_s-1×10^s-1+...+a₂×10²+a₁×10+a₀) mod d=a_s×r_s+a_s-1×r_s-1+ +… +a₂×r₂+a₁×r₁+a₀

Sformułowanie kryterium tekstem brzmi nieco zawile: reszta z dzielenia danej liczby przez d jest taka sama, jak reszta z dzielenia przez d sumy iloczynów jej kolejnych cyfr przez reszty z dzielenia odpowiednich potęg 10 przez d.

Konieczność wielokrotnego mnożenia i sumowania zniechęca do praktycznego korzystania z tak określonej cechy podzielności. Na szczęście, dla niektórych wartości d (3, 8, 9, 11) cechy udało się sformułować znacznie prościej, co wynika z ciągów w tabeli 1, zwłaszcza gdy są one stałe. Na przykład, z ciągu dla d=11 (1, –1, 1, –1, 1, –1,…) wynika odpowiednia cecha, polegająca na sprawdzeniu podzielności przez 11 sumy kolejnych cyfr danej liczby (od prawej do lewej), w której to sumie cyfry na parzystych miejscach występują ze znakiem ujemnym. Liczba 312 865 nie jest zatem wielokrotnością 11, ponieważ nie jest nią suma 5–6+8–2+1–3=3.

Siódemka jest pierwszym dzielnikiem, któremu odpowiada cecha podzielności niepoddająca się uproszczeniu po zastosowaniu kryterium Pascala. Biorąc na warsztat, na przykład, liczbę 312 865, trzeba uporać się z działaniem 5+6×3+8×2+2× (–1)+1×(–3)+3×(–2). Wprawdzie to nic trudnego, ale jednak wykonanie zwykłego dzielenia w słupku jest mniej kłopotliwe i szybsze.

Problem z siódemką stanowił od dawna inspirację do szukania innych sposobów formułowania cech podzielności. Efekty tych poszukiwań rzadko były w pełni zadowalające, jeśli chodzi o praktyczność i prostotę, ale zasługują na uwagę ze względu na odkrywczość i oryginalność zależności liczbowych, stanowiących ich podstawę.

Opis najstarszej cechy podzielności przez 7 znajduje się w Talmudzie, a ściślej w jednym z traktatów Talmudu zwanego babilońskim, powstałego w V wieku. Dotyczy obliczenia kolejności danego roku w tzw. cyklu szabasowym. Autor traktatu radzi: aby ustalić, czy liczba 100a+b jest podzielna przez 7, wystarczy sprawdzić podzielność przez 7 liczby 2a+b. Jeśli więc 2018=100a+b, to 2a+b=2×20+18=58, czyli o 2 więcej od wielokrotności siedmiu. Sposób jest skuteczny, ponieważ wynik działania 100a+b–(2a+b)=98a stanowi wielokrotność siedmiu, a zatem 2a+b jest podzielne przez 7 tylko wówczas, gdy przez 7 podzielne jest także 100a+b. Na podobnej zasadzie można tworzyć cechy podzielności liczby 100a+b przez inne liczby. Na przykład, dla d=11 wystarczyłoby sprawdzać podzielność liczby a+b, dla d=13 – liczby 9a+b lub b–4a, dla d=17 – liczby b–2a itd. Dla liczb dłuższych niż 4-cyfrowe korzystanie z takich cech byłoby jednak w wielu przypadkach zbyt uciążliwe.

Od schyłku średniowiecza cechowanie podzielności kusiło nie tylko matematyków, wśród których znaleźli się m.in. Fibonacci, Luca Pacioli i Peter Apianus. Autorem jednej z pierwszych prostych i osobliwych cech podzielności przez 7 był pod koniec XVII wieku francuski filozof Bernard Fontenelle. Zgodnie z jego koncepcją pierwszą cyfrę sprawdzanej liczby należy pomnożyć przez 3 i dodać do drugiej cyfry, a wynikiem zastąpić dwie pierwsze cyfry. Tę operację powtarza się aż do uzyskania dostatecznie małej, na przykład dwucyfrowej liczby, której podzielność przez 7 oznacza, że liczba wyjściowa oraz wszystkie tworzone w etapach pośrednich także są wielokrotnościami siedmiu. Ciąg wyników działań, zaczynający się od 312 865, przedstawiony jest na rys. 1. Nietrudno zauważyć, że podobnie jak w przypadku cechy z Talmudu efektywność tej metody wynika stąd, że po każdym działaniu liczba maleje o wielokrotność siedmiu.

W roku 1861 rosyjski matematyk Antoni Żbikowski (zrusyfikowany Polak, uczeń Czebyszewa) opisał inną oryginalną cechę podzielności przez 7, także wieloetapową, ale będącą w pewnym sensie przeciwieństwem poprzedniej, bowiem przy korzystaniu z niej liczby w kolejnych etapach „kurczą się” od tyłu. Konkretnie: w każdym etapie dwukrotność cyfry końcowej odejmowana jest od liczby pozostałej po usunięciu (odcięciu) ostatniej cyfry. Proces ten dla liczby startowej 312 865 przedstawia rys. 2.

Tym razem podstawę cechy podzielności przez 7 stanowi następująca zależność: 10a+b jest podzielne przez 7 wtedy i tylko wtedy, gdy przez 7 dzieli się a–2b. Wynika to z równania: 10a+b=10 (a–2b) +21b.

Główną zaletą metody Żbikowskiego jest to, że stanowi ona cechę podzielności uniwersalną, bowiem może być dostosowana do każdego dzielnika d względnie pierwszego z liczbą 10, czyli niepodzielnego przez 2 lub 5. Wystarczy utworzyć odpowiednie równanie, będące podstawą danej cechy. Na przykład, dla d=13 równaniem będzie 10a+b=10(a+4b)–39b, a instrukcją obsługi cechy podzielności polecenie: pomnóż końcową cyfrę przez 4 i dodaj do liczby krótszej o końcową cyfrę. Stosując dwukrotnie tę instrukcję do liczby 2028, otrzymamy w kolejnych etapach: 2028→234→39, a stąd wniosek, że skoro ostatnia liczba podzielna jest przez 13, to obie poprzednie także.

Podstawą metody Żbikowskiego jest znalezienie najmniejszej wielokrotności każdego dzielnika d – względnie pierwszego z 10, a więc zakończonego cyfrą 1, 3, 7 lub 9 – mającej postać 10k+1 – w wyniku pomnożenia go odpowiednio przez 1, 7, 3 i 9. Z kolei liczbę, której podzielność przez d jest badana, można zapisać w postaci 10a+b=10(a–kb)+(10k+1)b.

Ponieważ 10k+1 jest podzielne przez d, więc warunkiem podzielności przez d liczby 10a+b jest podzielność przez d wyrażenia a–kb. Stąd instrukcja: pomnóż ostatnią cyfrę przez k i odejmij od liczby a. Jeśli jednak okaże się, że k jest zbyt duże, a ściślej – większe od d/2, wówczas działania warto uprościć (jak w powyższym przykładzie dla d=13), zmieniając polecenie: pomnóż ostatnią cyfrę przez d–k i dodaj do liczby a. Podstawą tej zmiany jest inny zapis liczby 10a+b:

10a+b=10 [a+ (d–k) b]–10 db+ (10k+1)b

Analizując ogólną instrukcję, można dostosować ją do czterech konkretnych wariantów, czyli czterech rodzajów dzielników d zakończonych cyfrą – 1, 3, 7 lub 9.

Jeśli d=10c+1 (11, 21, 31, …), mnożymy przez k=c i odejmujemy.

Jeśli d=10c+3 (13, 23, 33, …), mnożymy przez d–k=3c+1 i dodajemy.

Jeśli d=10c+7 (7, 17, 27,…), mnożymy przez k=3c+2 i odejmujemy.

Jeśli d=10c+9 (19, 29, 39, …), mnożymy przez d–k=c+1 i dodajemy.

Korzystanie z metody Żbikowskiego w przypadku dużych liczb jest zwykle szybsze niż ręczne wykonywanie dzielenia, oczywiście jeśli celem jest tylko sprawdzenie podzielności, a nie wynik. Można się o tym samemu przekonać, sprawdzając obydwoma sposobami, czy uda się skrócić ułamek 67/5 865 582.

Na koniec warto przedstawić najnowszą, znaną od kilkunastu lat i chyba najbardziej osobliwą, choć nieprostą cechę podzielności przez 7. Korzystanie z niej zaczyna się od podziału sprawdzanej liczby – 357 902 468 – na grupy (liczby) dwucyfrowe – od prawej strony:

03|57|90|24|68

Grupy te ustawia się w odwrotnej kolejności:

68|24|90|57|03

i pod każdą zapisuje różnicę między nią a najbliższą wielokrotnością siedmiu, z tym, że dla liczb stojących na miejscach nieparzystych uwzględnia się mniejsze wielokrotności, a dla liczb na miejscach parzystych – wielokrotności większe:

54 663

Gdy liczba, jak w tym przypadku, jest więcej niż dwucyfrowa, cykl działań należy powtórzyć:

05|46|63

63|46|05

035

Finałem jest wielokrotność siedmiu, a więc liczba 357 902 468 także jest podzielna przez 7.

Dlaczego ta metoda jest skuteczna oraz, co równie ciekawe, dlaczego działa także jako cecha podzielności przez 11 i 13 – to zagadka do samodzielnego rozwiązania.

Zadania

1. Wzdłuż ośmiopiętrowej wieży kursuje dwuklatkowa winda (rys. 3). Po zatrzymaniu się na każdym n-tym piętrze cyfry na klatkach windy i na wieży (na rysunku zastąpione literami) tworzą trzycyfrową liczbę podzielną przez n+1, czyli liczba ABC na pierwszym piętrze dzieli się przez 2, ABD na drugim – przez 3, ABE na trzecim – przez 4 itd., aż do ósmego piętra, na którym pojawia się liczba ABJ podzielna przez 9.

Jaką cyfrę zastępuje każda z liter, jeśli wszystkie cyfry są różne?

Zadanie ma pięć rozwiązań. W czterech z nich AB=72 (CDEFGHIJ=np. 63450189). Jakie jest piąte rozwiązanie?

2. Jeśli do pól diagramu (rys. 4) wpiszemy dziesięć różnych cyfr, utworzą one liczby: jedną 2- i dwie 4-cyfrowe w wierszach oraz dwie 3-cyfrowe w kolumnach. Różne cyfry należy wpisać do diagramu tak, aby każda liczba za ukośnikiem obok diagramu była dzielnikiem liczby znajdującej się w wierszu przed nią lub w kolumnie nad nią. W rozwiązaniu wystarczy podać trzy liczby w rzędach.

3. Mam pięć różnych liczb całkowitych dodatnich mniejszych od 28:

a) żadna nie jest podzielna przez 3 ani przez 7;

b) żadna nie zawiera cyfry 3 ani 7;

c) żadna nie jest równa 10 (czyli 3+7);

d) suma prawie każdych dwu z nich jest podzielna przez 3 lub/i przez 7.

Słowo „prawie” w punkcie (d) oznacza, że tylko jedna z dziesięciu sum dwóch z tych liczb nie jest podzielna ani przez 3, ani przez 7.

Jakie to liczby?

4. Jaka liczba pięciocyfrowa jest 45 razy większa od iloczynu tworzących ją cyfr?

5. Liczbę 5 podniesiono do potęgi 23 456 789, a wynik potęgowania podzielono przez 7. Jaka była reszta z dzielenia?

6. Suma czterech różnych cyfr większych od zera podzielna jest przez 7. Z cyfr tych można utworzyć 24 różne liczby czterocyfrowe, ale żadna z nich nie będzie podzielna przez 7. Jakie to cyfry, jeśli nie są nimi kwartety [1, 2, 3, 8] ani [1, 3, 8, 9].

Rozwiązania prosimy nadsyłać do 31 października br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 10/18. Spośród autorów poprawnych rozwiązań przynajmniej trzech zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Liz Strachan Proste jak pi. Matematyka to bułka z masłem! ufundowaną przez wydawnictwo Prószyński Media.

Warunkiem udziału w konkursie jest zamieszczenie w e-mailu z odpowiedzią oświadczenia:

Zapoznałam/em się z regulaminem Konkursu i akceptuję jego treść oraz wyrażam zgodę na przetwarzanie danych osobowych na potrzeby realizacji Konkursu.

Regulamin Konkursu jest dostępny na stronie www.swiatnauki.pl

***

Rozwiązania zadań z numeru sierpniowego

1. Liczba kamieni leżących poziomo – 22. Pełne rozwiązanie na rys. 5.

2. Liczba kamieni leżących poziomo – 14. Pełne rozwiązanie na rys. 6.

3. Kolejne cyfry we wskazanym rzędzie – 4-4-3-5-3-0-5-5. Pełne rozwiązanie na rys. 7.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Elizabeth Tasker Fabryka planet. Egzoplanety i poszukiwanie drugiej Ziemi, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Bartosz Duński z Elbląga, Bartłomiej Goldman z Nadarzyna, Roman Kusyk z Lublina, Jerzy Siennicki z Warszawy i Robert Szewczak ze Szczytna.

***

Marek Penszko, z wykształcenia inż. poligrafii, jest znawcą i popularyzatorem gier i rozrywek umysłowych, głównie matematyki rekreacyjnej. Współpracuje z wieloma czasopismami, m.in. pisze blog dla Polityki.