Cecha podzielności

Cecha podzielności – metoda umożliwiająca stwierdzenie, czy dana liczba jest podzielna bez reszty przez inną. Są one narzędziami pomocniczymi ułatwiającymi sprawdzenie czynników liczby bez uciekania się do dzielenia. Choć podobne reguły mogą być ułożone dla dowolnej podstawy, to niżej zawarto tylko reguły dotyczące systemu dziesiętnego.

Cechy podzielności

Liczba całkowita jest podzielna:

• przez 1 – 1 jest zawsze dzielnikiem, więc mówienie o cesze podzielności jest niepotrzebne.
• przez 2 (jest liczbą parzystą), jeśli ostatnia z jej cyfr reprezentuje liczbę parzystą, czyli jest jedną z cyfr: 0, 2, 4, 6, 8.
• przez 3, jeśli suma cyfr tej liczby jest podzielna przez 3 – dzięki temu regułę można stosować rekurencyjnie aż do osiągnięcia liczby jednocyfrowej. Przykład: 104628: suma cyfr 1+0+4+6+2+8=21, 2+1=3, jest podzielna przez 3.
• przez 4, jeśli liczba tworzona przez jej dwie ostatnie cyfry jest podzielna przez 4. Przykład: 52136 bo 36/4=9 więc liczba 52136 jest podzielna przez 4. Natomiast wśród liczb mniejszych niż 100 podzielne przez 4 są te liczby, których:
  • pierwsza cyfra jest nieparzysta (1, 3, 5, 7 lub 9), a druga to 2 lub 6
  • pierwsza cyfra jest parzysta (0, 2, 4, 6 lub 8), a druga to 0, 4 lub 8
• przez 5, jeśli jej ostatnią cyfrą jest 0 lub 5.
• przez 6, jeśli jest podzielna zarówno przez 2, jak i przez 3.
• przez 7, jeśli suma jej cyfr mnożonych (od prawej) przez kolejne potęgi 3 (włącznie z potęgą zerową: 3⁰=1) jest podzielna przez 7. Przykład:

1757	:	1·27+7·9+5·3+7·1=112		1761	:	1·27+7·9+6·3+1·1=109
112	:	1·9+1·3+2·1=14		109	:	1·9+0·3+9·1=18
161	:	1·9+6·3+1·1=28		18	:	1·3+8·1=11
				11	:	1·3+1·1=4
Liczba 1757 oraz 112 i 161 są podzielne przez 7.				Liczba 1761 oraz 109, 18, 11 i 4 nie dzielą się przez 7.

• przez 8, jeśli liczba tworzona przez jej trzy ostatnie cyfry jest podzielna przez 8. Natomiast owa trzycyfrowa końcówka jest podzielna przez 8, jeśli składa się z następujących cyfr:

Cyfra setek	Cyfra dziesiątek	Cyfra jedności
0, 2, 4, 6 lub 8	0, 4 lub 8	0 lub 8
	1, 5 lub 9	6
	2, 6	4
	3, 7	2
1, 3, 5, 7 lub 9	0, 4 lub 8	4
	1, 5 lub 9	2
	2, 6	0 lub 8
	3, 7	6

• przez 9, jeśli suma cyfr tej liczby jest podzielna przez 9. Jeśli wynik sumowania jest wielocyfrowy sumowanie można powtarzać dla wyniku sumowania.

Przepis ten funkcjonuje nie tylko w zapisie dziesiętnym, ale również dla zapisów o innych niż 10 podstawach, jako kryterium podzielności przez liczbę o 1 mniejszą od podstawy.

• przez 10, jeśli jej ostatnią cyfrą jest 0.
• przez 11, jeśli po odjęciu od sumy cyfr stojących na miejscach nieparzystych, sumy cyfr stojących na miejscach parzystych otrzyma się liczbę podzielną przez 11. Nie ma znaczenia, czy miejsca parzyste i nieparzyste liczymy od lewej, czy od prawej. Przykład:

Liczba 737 → (7+7) – 3 = 14 – 3 = 11

737 jest podzielna przez 11

Przepis ten funkcjonuje nie tylko w zapisie dziesiętnym, ale również dla zapisów o innych niż 10 podstawach, jako kryterium podzielności przez liczbę o 1 większą od podstawy.

• przez 12, jeśli jest podzielna zarówno przez 3, jak i przez 4.
• przez 13, jeśli różnica liczby złożonej z trzech ostatnich cyfr i liczby złożonej z pozostałych cyfr jest podzielna przez 13, np. dla 85527 mamy 527 – 85 = 442, 442 / 13 = 34, więc liczba 85527 jest podzielna przez 13.
• przez 14, jeśli jest podzielna zarówno przez 2, jak i przez 7.
• przez 15, jeśli jest podzielna zarówno przez 3, jak i przez 5.
• przez 16, jeśli liczba tworzona przez jej cztery ostatnie cyfry jest podzielna przez 16.
• przez 18, jeśli jest podzielna zarówno przez 2, jak i przez 9.
• przez 20, jeśli jej ostatnia cyfra jest równa 0 a przedostatnia cyfra jest parzysta.
• przez 21, jeśli jest podzielna zarówno przez 3, jak i przez 7.
• przez 22, jeśli jest podzielna zarówno przez 2, jak i przez 11.
• przez 24, jeśli jest podzielna zarówno przez 3, jak i przez 8.
• przez 25, jeśli jej dwie ostatnie cyfry to 00, 25, 50 lub 75.
• przez 26, jeśli jest podzielna zarówno przez 2, jak i przez 13.
• przez 28, jeśli jest podzielna zarówno przez 4, jak i przez 7.
• przez 30, jeśli suma cyfr jest podzielna przez 3, a zapis dziesiętny liczby kończy się zerem.
• przez 32, jeśli liczba tworzona przez jej pięć ostatnich cyfr jest podzielna przez 32.
• przez 50, jeśli jej przedostatnia cyfra to 5 lub 0, a ostatnia to 0.
• przez 100, jeśli jej ostatnie dwie cyfry to 00.
• przez 2ⁿ, jeśli liczba utworzona z n jej ostatnich cyfr jest podzielna przez 2ⁿ.
• przez 5ⁿ, jeśli liczba utworzona z n jej ostatnich cyfr jest podzielna przez 5ⁿ.
• przez 10ⁿ, jeśli n jej ostatnich cyfr jest zerami.

Inne zasady:

• Inna cecha podzielności przez 7, 11 lub 13, oparta na równości $7\cdot 11\cdot 13=1001{:}$

grupujemy cyfry po 3 od końca i każdą taką grupę, poczynając od pierwszej z prawej, oznaczamy przez a1, a2, a3,... Dana liczba dzieli się przez 7, 11, 13 jeśli suma S = a1 – a2 + a3 – ... jest podzielna przez 7, 11, 13. Np. dla liczby x = 111220336444 mamy: 444−336+220−111=217, co dzieli się przez 7, a nie dzieli przez 11 i 13, zatem x dzieli się przez 7, a nie dzieli przez 11 ani przez 13.

• Liczba jest podzielna przez $n,$ jeśli jest ona podzielna przez $k$ i $l,n=k\cdot l$ oraz $k$ i $l$ są liczbami względnie pierwszymi.
• Liczba jest podzielna przez 2, 5 i 10 jeśli jej ostatnia cyfra to 0

Zasady te można udowodnić, używając kongruencji.

Liczby pierwsze

Z twierdzenia, że liczba jest podzielna przez $n,$ jeśli jest ona podzielna przez $k$ i $l,n=k\cdot l$ oraz $k$ i $l$ są względnie pierwsze, wiemy, że aby sprawdzić podzielność liczby, należy sprawdzić podzielność przez każdy z czynników dzielnika, np. podzielność 25116 przez 84 oznacza, że liczba ta powinna dzielić się przez każdą z liczb: 4, 3 i 7 (bo rozkład dzielnika na czynniki pierwsze ma postać: $84=2^{2}\cdot 3\cdot 7$) W tym kontekście ważne staje się ustalenie cech podzielności dla liczb pierwszych. Dość ogólną metodę konstruowania takich cech podzielności podaje Stephen Froggatt w serwisie Math Forum. Oto algorytm budowania cechy podzielności dla dowolnej liczby pierwszej p:

1. Szukamy najmniejszej liczby naturalnej $m,$ dla której $10\cdot m-1$ jest podzielne przez $p$ (inaczej: dla pewnego $k$ liczba $k\cdot p+1=10\cdot m$)
2. Wówczas, jak łatwo sprawdzić, $10\cdot (p-m)+1$ także dzieli się przez $p.$
3. Mamy do wyboru dwa sposoby postępowania:

a) od badanej liczby $x$ oddzielamy cyfrę jedności, mnożymy przez $m$ i dodajemy do pozostałej części liczby $x$ albo

b) od $x$ oddzielamy cyfrę jedności, mnożymy ją przez $m-p$ i odejmujemy od pozostałej części liczby $x.$

Jeśli otrzymana (mniejsza) liczba dzieli się przez $p,$ to i $x$ dzieli się przez $p.$ Jeśli otrzymana liczba jest jeszcze zbyt duża, można to postępowanie stosować wielokrotnie.

Zbudujmy np. cechę podzielności przez 7 (inną, niż opisana powyżej).

Ponieważ 10·5−1=49 dzieli się przez 7, więc m=5 i aby zbadać, czy liczba 25116 dzieli się przez 7 postępujemy następująco: Oddzielamy cyfrę jedności: 6 i obliczamy: 2511+6·5 = 2541. Powtarzamy ten krok jeszcze dwukrotnie:254+1·5 = 259; 25+9·5 = 70, co dzieli się przez 7. Zatem liczba 25116 dzieli się przez 7 (a jak łatwo sprawdzić, dzieli się też przez 4 i 3, więc dzieli się przez 84).

Analogicznie działa wersja (b): m−p=7−5=2, więc: 2511−6·2=2499; 249−9·2=231; 23−1 ·2=21, co dzieli się przez 7, więc badana liczba 25116 dzieli się przez 7.

Poniższa tabelka podaje czynniki $m$ oraz $p-m$ dla liczb pierwszych z zakresu $6<p<100.$

dzielnik pierwszy $p$	czynnik $m$	czynnik $p-m$	zalecany algorytm
7	5	2	(-2c) lub (+5c)
11	10	1	[-1c] lub (+10c)
13	4	9	(+4c)
17	12	5	(−5c)
19	2	17	(+2c)
23	7	16	(+7c)
29	3	26	(+3c)
31	28	3	(−3c)
37	26	11	(−11c)
41	37	4	(−4c)
47	33	14	(−14c) lub (+33c)
53	16	37	(+16c)
59	6	53	(+6c)
61	55	6	(−6c)
67	47	20	(−20c)
71	64	7	(−7c)
73	22	51	(+22c)
79	8	71	(+8c)
83	25	58	(+25c)
89	9	80	(+9c) lub (−80c)
97	68	29	(+68c) lub (−29c)

itd.

W kolumnie „zalecany algorytm” zapis: (+6c) oznacza: „pomnóż ostatnią cyfrę przez 6 i dodaj do pozostałej części liczby”, a (−7c) – „pomnóż ostatnią cyfrę przez 7 i odejmij od pozostałej części liczby”. Zalecany wybór wariantu algorytmu podyktowany jest przede wszystkim wygodą wykonania jednego z wariantów mnożenia.

Odrębnym, znacznie trudniejszym zagadnieniem jest badanie podzielności i rozkładanie na czynniki, czyli faktoryzacja bardzo dużych liczb (to znaczy liczb stucyfrowych i większych). Tego typu rozkłady znalazły zastosowanie w kryptografii. Jednak zadanie rozkładu na czynniki pierwsze liczb o 100 i więcej cyfrach jest trudne (złożone obliczeniowo) – nie są znane żadne algorytmy o zadowalającej szybkości, mimo że nowe algorytmy wykorzystują wiele głębokich rezultatów teorii liczb.

Wyznaczanie

Jedną z metod wyznaczania cech podzielności przez $n,$ gdzie $n$ jest liczbą pierwszą lub potęgą takowej, jest zbadanie odwrotności owej liczby. Zachodzą tu dwie możliwości:

1. otrzymujemy ułamek okresowy o długości okresu $k$ cyfr. Dana liczba jest podzielna przez $n,$ gdy suma $k$-cyfrowych grup dzieli się przez $n.$

   Np. niech $n=7;$ odwrotność $1/n=0{,}(142857)$ – długość okresu $k=6$

   Liczba 864197523713913580247 jest podzielna przez 7 bo: 000864 + 197523 + 713913 + 580247 = 1492547, dalej: 000001 + 492547 = 492548 i 492548 / 7 = 70364

2. otrzymujemy liczbę o $k$ cyfrach po przecinku. Dana liczba jest podzielna przez $n,$ gdy liczba z $k$ ostatnich cyfr tej liczby dzieli się przez $n.$

   Np. niech $n=8,$ odwrotność $1/n=0{,}125$ – mamy trzy cyfry po przecinku, czyli liczba dzieli się przez 8 gdy liczba z jej trzech ostatnich cyfr się dzieli.

Ten przepis funkcjonuje we wszystkich potęgowych systemach pozycyjnych.

Np. cechę podzielności przez 5 dla liczb w zapisie dwójkowym wyznaczamy następująco:

$1/5=0{,}2=0{,}(0011)_{2}$ – długość okresu $k=4,$ więc dana liczba jest podzielna przez 5 gdy suma 4-cyfrowych grup dzieli się przez 5.

Cechę podzielności przez 4 dla liczb w zapisie szesnastkowym wyznaczamy podobnie:

$1/4=0{,}4_{16}$ – mamy jedną cyfrę po przecinku, czyli liczba dzieli się przez 4 gdy liczba zapisana jej ostatnią cyfrą się dzieli.

Dowody podzielności przez 9 i 11

Jeżeli $w(x)$ jest wielomianem całkowitym względem $x$ o współczynnikach całkowitych, to kongruencja $a\equiv b{\pmod {m}}$ pociąga za sobą $w(a)\equiv w(b){\pmod {m}}.$

Niech $A_{0}x^{n}+A_{1}x^{n-1}+A_{2}x^{n-2}+\ldots +A_{n-1}x+A_{n}$ będzie wielomianem całkowitym $n$-tego stopnia o współczynnikach całkowitych (wielomian ten oznaczamy krótko przez $w(x)$), $m$ będzie danym modułem, zaś $a$ i $b$ liczbami całkowitymi przystającymi według modułu $m.$ Zapiszemy ciąg kongruencji następująco:

$A_{0}a^{n}\equiv A_{0}b^{n}{\pmod {m}},$

$A_{1}a^{n-1}\equiv A_{1}b^{n-1}{\pmod {m}},$

$A_{n-1}a\equiv A_{n-1}b{\pmod {m}},$

$A_{n}\equiv A_{n}{\pmod {m}}.$

Dodajemy stronami,

$A_{0}a^{n}+A_{1}a^{n-1}+\dots +A_{n-1}a+A_{n}\equiv A_{0}b^{n}+A_{1}b^{n-1}+\dots +A_{n-1}b+A_{n}{\pmod {m}},$ czyli

$w(a)\equiv w(b){\pmod {m}}.$

Niech $N\in \mathbb {N} ,$ a $C_{1},C_{2},C_{3},\dots ,C_{n}\quad {}$ jej kolejnymi cyframi w układzie dziesiętnym.

$N=C_{1}10^{n-1}+C_{2}10^{n-2}+\ldots +C_{n-1}10+C_{n}.$

Niech

• $w(x)=C_{1}x^{n-1}+C_{2}x^{n-2}+\ldots +C_{n-1}x+C_{n}$

i

• $w(10)=N.$

Podzielność przez 9

Z lematu i wobec kongruencji $10\equiv 1{\pmod {9}}\quad {}$ mamy

$w(1)=C_{1}+C_{2}+\ldots +C_{n-1}+C_{n},$

zatem

$N\equiv C_{1}+C_{2}+C_{3}+\ldots +C_{n-1}+C_{n}{\pmod {9}},$

co dowodzi, że każda liczba naturalna przystaje według modułu $9$ do sumy swoich cyfr. Dla podzielności liczby $N$ przez $9$ wystarcza, by suma jej cyfr była podzielna przez $9.$

Podzielność przez 11

Wobec lematu oraz kongruencji $10\equiv -1{\pmod {11}},$ mamy

$w(10)\equiv w(-1){\pmod {11}},$

czyli

$N\equiv C_{1}-C_{2}+C_{3}-C_{4}+\dots {\pmod {11}}.$

Co oznacza podzielność przez $11{:}$ liczba jest podzielna przez 11, jeśli po odjęciu sumy cyfr stojących na miejscach nieparzystych od sumy cyfr stojących na miejscach parzystych otrzymamy liczbę podzielną przez 11.

Bibliografia

• Witryna Math Forum @Drexel (ang.)
• Cechy podzielności. [dostęp 2008-09-28].

Linki zewnętrzne

• Wiktor Bartol, Jak znaleźć cechy podzielności, Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej (MiNI PW), kanał „Archipelag Matematyki” na YouTube, 31 sierpnia 2017 [dostęp 2024-09-04].
• Eric W.E.W. Weisstein Eric W.E.W., Divisibility Tests, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-02-02].