Cechy podzielności

Najzgrabniej wyprowadza się cechy podzielności za pomocą pochodzącego od Gaussa pojęcia kongruencji: dana jest liczba naturalna m > 1, która nazywa się modułem; o dwóch liczbach całkowitych a i b mówimy, że przystają do siebie modulo n, a $\equiv$ b(modm), gdy a i b dają tę samą resztę z dzielenia przez m - lub, równoważnie, gdy róznica a - b dzieli się przez m. Aby nie straszyć nowym, obco brzmiącym pojęciem, będziemy mówić o równości reszt.

Dana jest liczba m i zapisana w dziesiętnym układzie pozycyjnym liczba

x = a_s ^. 10^s + a_s-1 ^. 10^s-1 +...+ a₂ ^. 100 + a₁ ^. 10 + a₀.

Cecha podzielności przez m to sposób obliczania reszty z dzielenia x przez m. Tylko zamiast jak zwykle sprawdzać podzielność przez m dzieleniem z resztą, sprytnie wykorzystuje się cyfry zapisu a_sa_s-1...a₂a₁a₀, aby obliczyć łatwo resztę z dzielenia x przez m mniejszym nakładem pracy. Polega to na zastępowaniu liczby x przez mniejsze liczby, dające tę samą resztę z dzielenia przez m, czyli przystające do x modulo m.

Metoda wykorzystuje dwie proste obserwacje:

1. Jeśli a, a' dają tę samą resztę z dzielenia przez m, i b, b' dają tę samą resztę z dzielenia przez m, to a + b i a' + b' dają tę samą resztę z dzielenia przez m.
2. Jeśli a, a' dają tę samą resztę z dzielenia przez m, i b, b' dają tę samą resztę z dzielenia przez m, to a ^. b i a' ^. b' dają tę samą resztę z dzielenia przez m.

Najprostszy przypadek podzielności przez 2 analizujemy tak, żeby był przykładem ogólnej zasady.

Cecha podzielności przez m = 2. 10 daje resztę 0 z dzielenia przez 2. Wobec tego 10 ^. 10 daje taką samą resztę jak 0 ^. 0, czyli 0. Podobnie resztę 0 dają wszystkie wyższe potęgi 10:

10^k+1 = 10^{k .} 10

daje taką samą resztę jak 0 ^. 0, czyli 0. Wobec tego a_k ^. 10^k daje taką samą resztę z dzielenia przez 2 jak a_k ^. 0 dla k > 0 - po prostu liczba a_k ^. 10^k jest parzysta dla k > 0. Teraz przypominamy sobie, że

x = a_s ^. 10^s + a_s-1 ^. 10^s-1 +...+ a₂ ^. 100 + a₁ ^. 10 + a₀

- liczba x daje taką samą resztę z dzielenia przez 2, jak 0 + 0 + ... +0 + a₀. Wobec tego x $\equiv$ a₀(mod2), czyli liczba naturalna x daje taką samą resztę z dzielenia przez 2, jak jej cyfra jedności.

Cecha podzielności przez m = 3. Obliczyczmy reszty z dzielenia przez 3 kolejnych potęg dziesiątki: 1 = 10⁰ daje resztę 1 z dzielenia przez 3, 10 = 10¹ daje resztę 1 z dzielenia przez 3, jeśli 10^k daje resztę 1 z dzielenia przez 3, to 10^k+1 = 10 ^. 10^k daje taką samą resztę z dzielenia przez 3, jak 1 ^. 1 = 1. Zatem a_k ^. 10^k daje taką samą resztę z dzielenia przez 3 jak a_k ^. 1 = a_k. Stąd

x = a_s ^. 10^s + a_s-1 ^. 10^s-1 +...+ a₂ ^. 100 + a₁ ^. 10 + a₀

daje taką samą resztę z dzielenia przez 3, jak a_s + a_s-1 + ... + a₂ + a₁ + a₀. Zatem liczba naturalna x daje taką samą resztę z dzielenia przez 3, jak suma jej cyfr.

Cecha podzielnosci przez m = 4. Znana cecha podzielności przez 4 powstaje tak: 1 = 10⁰ daje resztę 1 z dzielenia przez 4, 10 = 10¹ daje taką samą resztę z dzielenia przez 4, jak 10, 100 = 10² daje resztę 0 z dzielenia przez 4, dla k > 1 liczba 10^k+1 = 10 ^. 10^k daje taką samą resztę z dzielenia przez 4, jak 10 ^. 0 = 0. Zatem liczba naturalna x daje taką samą resztę z dzielenia przez 4, jak liczba a₁ ^. 10 + a₀.

Można zauwazyć, że 10 daje resztę 2 z dzielenia przez 4, lub że 10 daje taką samą resztę z dzielenia przez 4, jak -2, i uzyskać nowe cechy podzielnosci przez 4: liczba naturalna x daje taką samą resztę z dzielenia przez 4, jak liczba 2 ^. a₁ + a₀ i jak liczba a₀ -2 ^. a₁.

Cecha podzielności przez m = 5. Podobnie jak w przypadku podzielności przez 2, dla k > 1 liczba 10^k dzieli się przez 5, więc liczba naturalna x daje taką samą resztę z dzielenia przez 5, jak jej cyfra jedności.

Cecha podzielności przez m = 6. Oczywiście 6 = 2 ^. 3 i liczby 2, 3 są względnie pierwsze, wiec x dzieli się przez 6 wtedy i tylko wtedy, kiedy dzieli się przez 2 i dzieli się przez 3. Ale można łatwo obliczyć resztę z dzielenia x przez 6: 10 daje resztę 4 z dzielenia przez 6, jeśli 10^k daje resztę 4 z dzielenia przez 6, to 10^k+1 = 10 ^. 10^k daje taką samą resztę z dzielenia przez 6, jak 4 ^. 4 = 16, to znaczy daje resztę 4. Liczba

x = a_s ^. 10^s + a_s-1 ^. 10^s-1 +...+ a₂ ^. 100 + a₁ ^. 10 + a₀

daje taką samą resztę z dzielenia przez 6, jak a_s ^. 4 + a_s-1 ^. 4 +...+ a₂ ^. 4 + a₁ ^. 4 + a₀.

Cecha podzielności przez m = 7. 1 daje resztę 1; 10 daje resztę 3; 10² daje taką samą resztę, jak 3² czyli resztę 2; 10³ daje taką samą resztę, jak 3 ^. 2, czyli taką samą resztę, jak -1; 10⁴ daje taką samą resztę, jak 3 ^. (- 1), czyli taką samą resztę, jak -3; 10⁵ daje taką samą resztę, jak 3 ^. (- 3), czyli taką samą resztę, jak -2; 10⁶ daje taką samą resztę, jak 3 ^. (- 2), czyli resztę 1. Oczywiście dalej reszty powtarzają się okresowo. Rozumując jak poprzednio, stwierdzamy, że aby obliczyć resztę z dzielania x przez 7, trzeba - zaczynając od rzędu jedności - mnożyć jej cyfry przez wyrazy ciągu okresowego 1, 3, 2, -1, -3, -2, 1, 3, 2, -1, -3, -2, 1, ..., dodać do siebie obliczone iloczyny i obliczyc resztę z dzielenia tak otrzymanej liczby przez 7. Np. 1001 daje taką samą resztę, jak 1 ^. 1 + 3 ^. 0 + 2 ^. 0 + (- 1) ^. 1 = 0, czyli 1001 dzieli się przez 7. Podobnie 1000000001 dzieli się przez 7.

Cecha podzielności przez m = 8. Podobnie jak w przypadku m = 4 od pewnego miejsca potęgi dziesiątki dzielą sie przez 8, więc liczba naturalna x daje taką samą resztę z dzielenia przez 8, jak liczba a₂ ^. 100 + a₁ ^. 10 + a₀.

Ponadto 10 daje resztę 2 z dzielenia przez 8, więc 100 daje taką samą resztę, jak 2 ^. 2 = 4 i liczba naturalna x daje taką samą resztę z dzielenia przez 8, jak liczba a₂ ^. 4 + a₁ ^. 2 + a₀.

Cecha podzielności przez m = 9. Obliczymy reszty z dzielenia przez 9 kolejnych potęg dziesiątki: 1 = 10⁰ daje resztę 1 z dzielenia przez 9, 10 = 10¹ daje resztę 1 z dzielenia przez 9, jeśli 10^k daje resztę 1 z dzielenia przez 9, to 10^k+1 = 10 ^. 10^k daje taką samą resztę z dzielenia przez 9, jak 1 ^. 1 = 1. Zatem a_k ^. 10^k daje taką samą resztę z dzielenia przez 9 jak a_k ^. 1 = a_k.

x = a_s ^. 10^s + a_s-1 ^. 10^s-1 +...+ a₂ ^. 100 + a₁ ^. 10 + a₀

daje taką samą resztę z dzielenia przez 9, jak a_s + a_s-1 +...+ a₂ + a₁ + a₀. Zatem liczba naturalna x daje taką samą resztę z dzielenia przez 9, jak suma jej cyfr.

Cecha podzielności przez m = 10. Podobnie jak w przypadku m = 2 i m = 5 jeśli k > 0, to 10^k daje resztę 0 z dzielenia przez 10. Wobec tego liczba naturalna x daje taką samą resztę z dzielenia przez 10, jak jej cyfra jedności. Albo: reszta z dzielenia x przez 10 jest jej cyfrą jedności.

Cecha podzielnosci przez m = 11. 1 = 10⁰ daje resztę 1 z dzielenia przez 11; 10 = 10¹ daje taką samą resztę z dzielenia przez 11 jak -1; 100 = 10² daje taką samą resztę z dzielenia przez 11 jak -1 ^. (- 1) = 1 i dalej reszty z dzielenia przez 11 poteg 10 powtarzają się cyklicznie (okresowo).

x = a_s ^. 10^s + a_s-1 ^. 10^s-1 +...+ a₂ ^. 100 + a₁ ^. 10 + a₀

daje taką samą resztę z dzielenia przez 11, jak znakozmienna suma a₀ - a₁ + a₂ -...+ (- 1)^s-1a_s-1 + (- 1)^sa_s. Zatem liczba x daje taką samą resztę z dzielenia przez 11, jak róznica sumy jej cyfr z rzędów parzystych i sumy jej cyfr z rzedów nieparzystych.

Na przyklad 1001 dzieli się przez 11 i 1000000001 dzieli się przez 11.

Cecha podzielności przez m = 12. Oczywiście 12 = 3 ^. 4 i liczby 3, 4 są względnie pierwsze, więc x dzieli się przez 12 wtedy i tylko wtedy, kiedy dzieli się przez 3 i dzieli się przez 4.

Cecha podzielnosci przez m = 13. 1 daje resztę 1; 10 daje taką samą resztę, jak -3; 10² daje taką samą resztę, jak (- 3)² = 9, czyli taką samą resztę, jak -4; 10³ daje taką samą resztę, jak (- 3) ^. (- 4) = 12, czyli taką samą resztę, jak -1; 10⁴ daje taką samą resztę, jak (- 3) ^. (- 1), czyli taką samą resztę, jak 3; 10⁵ daje taką samą resztę, jak (- 3) ^. 3 = - 9, czyli taką samą resztę, jak 4; 10⁶ daje taką samą resztę, jak (- 3) ^. 4, czyli resztę 1. Oczywiście dalej reszty powtarzają się okresowo. Rozumując jak poprzednio, stwierdzamy, że aby obliczyć resztę z dzielenia x przez 13, trzeba - zaczynając od rzędu jedności - mnożyc jej cyfry przez wyrazy ciągu okresowego 1, -3, -4, -1, 3, 4, 1, -3, -2, -1, 3, 4, 1,... dodać do siebie obliczone iloczyny i obliczyć resztę z dzielenia tak otrzymanej liczby przez 13.

Na przykład 1001 daje taką samą resztę, jak 1 ^. 1 - 3 ^. 0 - 4 ^. 0 + (- 1) ^. 1 = 0, czyli 1001 dzieli się przez 13. Podobnie 1000000001 dzieli się przez 13.

Cecha podzielności przez m = 14. Oczywiście 14 = 2 ^. 7 i liczby 2, 7 są względnie pierwsze, więc x dzieli się przez 14 wtedy i tylko wtedy, kiedy dzieli się przez 2 i dzieli się przez 7.

Cecha podzielności przez m = 15. Oczywiście 15 = 3 ^. 5 i liczby 3, 5 są względnie pierwsze, więc x dzieli się przez 15 wtedy i tylko wtedy, kiedy dzieli się przez 3 i dzieli się przez 5.

W podobny sposób możemy opracować cechy podzielności przez dowolne liczby.