Kritéria dělitelnosti Jaroslav Zhouf, Pedf UK Praha
Kritéria dělitelnosti slouží k rozhodování o tom, zda je určité přirozené číslo n dělitelné určitým přirozeným číslem k. Každé takové kritérium se snaží nahradit dané číslo n jiným, zpravidla menším číslem n´, u něhož je již jednoduché rozhodnout o dělitelnosti číslem k. Pokud by n´ nebylo ještě vhodné, lze na něj aplikovat kritérium dělitelnosti znovu atd. Veškeré další úvahy budou vycházet z dekadického zápisu přirozeného čísla n = ...a5 a4 a3 a2 a1a0 , kde a0 , a1 , a2 , a3 , … jsou cifry, tj. ze zápisu
n = ... + 105 a5 + 104 a4 + 103 a3 + 102 a2 + 10a1 + a0 . A. Dělitelnost určovaná pomocí posledních cifer
Ze zápisu n = (... + 104 a5 + 103 a4 + 102 a3 + 10a2 + a1 ) ⋅10 + a0 je patrné, že poslední cifra a0
rozhoduje o dělitelnosti čísla n všemi děliteli čísla 10, tj. čísly 2, 5 a 10 (číslo 1 zde, ani nadále neuvažujeme), neboť číslo (... + 104 a5 + 103 a4 + 102 a3 + 10a2 + a1 ) ⋅10 čísly 2, 5 a 10 dělitelné je. Ze zápisu n = (... + 103 a5 + 102 a4 + 10a3 + a2 ) ⋅100 + a1a0 je stejně tak patrné, že poslední
dvojčíslí a1a0 rozhoduje o dělitelnosti čísla n všemi děliteli čísla 100, tj. čísly 2, 4, 5, 10, 20, 25, 50 a 100. (Na školách se vyslovuje většinou jen dělitelnost čtyřmi.) Analogicky poslední trojčíslí a2 a1a0 rozhoduje o dělitelnosti všemi děliteli čísla 1 000, tj. čísly 2, 4 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500 a 1 000. (Na školách se opět vyslovuje jen dělitelnost osmi.) Poslední čtyřčíslí rozhoduje o dělitelnosti všemi děliteli čísla 10 000, mimo jiné o dělitelnosti šestnácti. Kritéria dělitelnosti určované pomocí posledního pětičíslí, šestičíslí atd. se vysloví analogicky. B. Dělitelnost čísly složenými z několika nesoudělných dělitelů
Dělitelnost šesti se určuje pomocí dělitelnosti dvěma a třemi, dělitelnost deseti se určuje pomocí dělitelnosti dvěma a pěti, dělitelnost dvanácti se určuje pomocí dělitelnosti třemi a čtyřmi, dělitelnost šedesáti se určuje pomocí dělitelnosti třemi, čtyřmi a pěti atd. C. Dělitelnost určovaná pomocí součtu celočíselných násobků jednotlivých cifer (pomocí celočíselné lineární kombinace jednotlivých cifer)
Ukážeme univerzální metodu vytváření kritérií dělitelnosti libovolným přirozenými čísly. Pro každého dělitele můžeme takto vytvořit libovolné množství kritérií. Z nich samozřejmě vybereme to nejjednodušší. Teoreticky je však možné použít kterékoli z nich.
Dělitelnost
dvěma
Jelikož n = (... + 50 000a5 + 5 000a4 + 500a3 + 50a2 + 5a1 ) ⋅ 2 + a0 , je číslo n dělitelné dvěma, právě když je dělitelná dvěma cifra a0 . Tento postup nepřináší nové kritérium. Dělitelnost
třemi
Číslo n = (.. + 33 333a5 + 3 333a4 + 333a3 + 33a2 + 3a1 ) ⋅ 3 + (.. + a5 + a4 + a3 + a2 + a1 + a0 ) je dělitelné třemi, právě když je třemi dělitelný ciferný součet ... + a5 + a4 + a3 + a2 + a1 + a0 čísla n. Dělitelnost
čtyřmi
Jelikož n = (... + 25 000a5 + 2 500a4 + 250a3 + 25a2 + 2a1 ) ⋅ 4 + 2a1 + a0 , je číslo n dělitelné čtyřmi, právě když je dělitelné čtyřmi číslo 2a1 + a0 . Příklad: Je-li n = 5 835 , je 2a1 + a0 = 2 ⋅ 3 + 5 = 11 . Jelikož číslo 11 není dělitelné čtyřmi, není čtyřmi dělitelné ani číslo 5835. Každý si může rozmyslet, které z obou uvedených kritérií dělitelnosti čtyřmi je v tomto případě výhodnější. Ukážeme si ještě na dělitelnosti čtyřmi, jak můžeme vytvářet další kritéria. Při úpravě n = (... + 25 000a5 + 2 500a4 + 250a3 + 25a2 + a1 ) ⋅ 4 + 6a1 + a0 vidíme, že číslo n je dělitelné čtyřmi,
právě
když
je
čtyřmi
dělitelné
číslo
6a1 + a0 .
Při
úpravě
n = (... + 25 000a5 + 2 500a4 + 250a3 + 25a2 + 3a1 ) ⋅ 4 − 2a1 + a0 vidíme, že číslo n je dělitelné
čtyřmi, právě když je čtyřmi dělitelné číslo −2a1 + a0 . Takže zkoumání čísla −2a1 + a0 může být také výhodné, protože toto číslo může být menší než číslo 2a1 + a0 . Podobné úpravy čísla n můžeme provádět dále, čímž můžeme vytvořit libovolné množství kritérií dělitelnosti čtyřmi. Dělitelnost
pěti
Dělitelnost pěti se zkoumá podobně jako dělitelnost dvěma. Je to velmi jednoduchý výpočet, proto ho zde provádět nebudeme. Dělitelnost Platí
šesti
n = (... + 1 666a4 + 166a3 + 16a2 + a1 ) ⋅ 6 + (... + 4a5 + 4a4 + 4a3 + 4a2 + 4a1 + a0 ) =
= (... + 16 667 a5 + 1 667 a4 + 167 a3 + 17 a2 + 2a1 ) ⋅ 6 + (... − 2a5 − 2a4 − 2a3 − 2a2 − 2a1 + a0 ) . Číslo
n je dělitelné šesti, právě když je dělitelné šesti číslo ... + 4a5 + 4a4 + 4a3 + 4a2 + 4a1 + a0 nebo číslo ... − 2a5 − 2a4 − 2a3 − 2a2 − 2a1 + a0 . Příklad: Je-li n = 28 434 , je 4 ⋅ 2 + 4 ⋅ 8 + 4 ⋅ 4 + 4 ⋅ 3 + 4 = 72 a dále 4 ⋅ 7 + 2 = 30 a dále 4 ⋅ 3 + 0 = 12 a dále 4 ⋅1 + 2 = 6 , což je číslo dělitelné šesti, a proto je dělitelné šesti i číslo 28 434. Nebo −2 ⋅ 2 − 2 ⋅ 8 − 2 ⋅ 4 − 2 ⋅ 3 + 4 = −30 , což je číslo dělitelné šesti, a proto je dělitelné šesti i číslo 28 434.
Dělitelnost sedmi Platí
n = (... + 1 428a4 + 142a3 + 14a2 + a1 ) ⋅ 7 + (... + 5a5 + 4a4 + 6a3 + 2a2 + 3a1 + a0 ) =
= (... + 14 286a5 + 1 429a4 + 142a3 + 14a2 + a1 ) ⋅ 7 + (... − 2a5 − 3a4 − a3 + 2a2 + 3a1 + a0 ) . Číslo n je
dělitelné sedmi, právě když je dělitelné sedmi číslo ... + 5a5 + 4a4 + 6a3 + 2a2 + 3a1 + a0 nebo číslo ... − 2a5 − 3a4 − a3 + 2a2 + 3a1 + a0 . Příklad: Je-li n = 28 434 , je 4 ⋅ 2 + 6 ⋅ 8 + 2 ⋅ 4 + 3 ⋅ 3 + 4 = 77 , což je číslo dělitelné sedmi, a proto je dělitelné sedmi i číslo 28 434. Nebo −3 ⋅ 2 − 8 + 2 ⋅ 4 + 3 ⋅ 3 + 4 = 7 , což je číslo dělitelné sedmi, a proto je dělitelné sedmi i číslo 28 434.
Dělitelnost osmi Platí n = (... + 12 500a5 + 1 250a4 + 125a3 + 12a2 + a1 ) ⋅ 8 + 4a2 + 2a1 + a0 . Číslo n je dělitelné osmi, právě když je dělitelné osmi číslo 4a2 + 2a1 + a0 . Příklad: Je-li n = 425 328 , je 4 ⋅ 3 + 2 ⋅ 2 + 8 = 24 , což je číslo dělitelné osmi, proto je dělitelné osmi i číslo 425 328. Dělitelnost devíti Číslo
n = (.. + 11111a5 + 1111a4 + 111a3 + 11a2 + a1 ) ⋅ 9 + (.. + a5 + a4 + a3 + a2 + a1 + a0 )
je
dělitelné devíti, právě když je devíti dělitelný ciferný součet ... + a5 + a4 + a3 + a2 + a1 + a0 čísla n. Dělitelnost
deseti
Dělitelnost deseti se zkoumá podobně jako dělitelnost dvěma. Je to velmi jednoduchý výpočet, proto ho zde provádět nebudeme. Dělitelnost
jedenácti
Platí n = (... + 9 091a5 + 909a4 + 91a3 + 9a2 + a1 ) ⋅11 + (... − a5 + a4 − a3 + a2 − a1 + a0 ) . Číslo n je dělitelné jedenácti, právě když je dělitelné jedenácti číslo ... − a5 + a4 − a3 + a2 − a1 + a0 , tj. právě když je dělitelný jedenácti rozdíl součtu cifer na sudých místech a součtu cifer na lichých místech. Příklad: Je-li n = 1 234 567 , je ( 7 + 5 + 3 + 1) − ( 6 + 4 + 2 ) = 2 , což není číslo dělitelné jedenácti, proto není dělitelné jedenácti ani číslo 1 234 567. Dělitelnost
dvanácti
Platí n = (... + 833a4 + 83a3 + 8a2 + a1 ) ⋅12 + (... + 4a5 + 4a4 + 4a3 + 4a2 − 2a1 + a0 ) . Číslo n je dělitelné dvanácti, právě když je dělitelné dvanácti číslo ... + 4a5 + 4a4 + 4a3 + 4a2 − 2a1 + a0 . Dělitelnost dalšími přirozenými čísly se vytvoří analogicky. Vše je pro několik nejmenších přirozených čísel shrnuto v následující tabulce. Je dobré všimnout si v této tabulce periodicity
koeficientů a případné předperiody vytvořené z koeficientů u jednotlivých cifer. Tabulka zbytků vyjadřující kritéria dělitelnosti jednotlivými přirozenými čísly: Dělitel nost čísla ...a4 a3a2 číslem
Kritérium dělitelnosti
2
a0
3
... + a4 + a3 + a2 + a1 + a0
4
2a1 + a0
5
a0
6
... + 4a4 + 4a3 + 4a2 + 4a1 + a0
7
... + 3a7 + a6 − 2a5 − 3a4 − a3 + 2a2 + 3a1 + a0
8
4a2 + 2a1 + a0
9
... + a4 + a3 + a2 + a1 + a0
10
a0
11
... + a4 − a3 + a2 − a1 + a0
12
...4a4 + 4a3 + 4a2 − 2a1 + a0
13
... − 3a7 + a6 + 4a5 + 3a4 − a3 − 4a2 − 3a1 + a0
14
... + 2a8 − 4a7 − 6a6 − 2a5 + 4a4 + 6a3 + 2a2 − 4a1 + a0
15
... − 5a3 − 5a2 − 5a1 + a0
16
8a3 + 4a2 − 6a1 + a0
17
... + 2a10 + 7a9 − a8 + 5a7 − 8a6 + 6a5 + 4a4 − 3a3 − 2a2 − 7a1 + a0
18
... − 8a3 − 8a2 − 8a1 + a0
19
... + 9a10 − a9 − 2a8 − 4a7 − 8a6 + 3a5 + 6a4 − 7a3 + 5a2 − 9a1 + a0
20
10a1 + a0
21
... + 10a7 + a6 − 2a5 + 4a4 − 8a3 − 5a2 + 10a1 + a0
22
... − 10a4 + 10a3 − 10a2 + 10a1 + a0
23 24
... − 10a12 − a11 − 7a10 − 3a9 + 2a8 − 9a7 + 6a6 − 4a5 − 5a4 + 11a3 + 8a2 + 10a1 + ... − 8a5 − 8a4 − 8a3 + 4a2 + 10a1 + a0
10a1 + a0
25
Úloha: Analogicky vytvořte pokračování výše uvedené tabulky pro další dělitele. D. Dělitelnost určovaná pomocí součtu celočíselných násobků dvojčíslí, trojčíslí, … (pomocí celočíselné lineární kombinace dvojčíslí, trojčíslí, …)
Budeme postupovat analogicky jako v oddíle C, budeme si ale všímat dvojčíslí, trojčíslí, … vzniklých rozdělením zadaného přirozeného čísla od konce po dvojicích, po trojicích, … Dvojčíslí Můžeme také psát n = ... + 10 000 ⋅ a5 a4 + 100 ⋅ a3 a2 + a1a0 . Když se tento zápis upraví na tvar
(
)
(
)
n = ... + 101⋅ a5 a4 + a3 a2 ⋅ 99 + ... + a5 a4 + a3 a2 + a1a0 ,
lze
odtud
vyslovit
kritéria
dělitelnosti všemi děliteli čísla 99, tj. čísly 3, 9, 11, 33 a 99. Např.: Číslo n je dělitelné jedenácti, právě když je jedenácti dělitelné číslo ... + a5 a4 + a3 a2 + a1a0 , tj. právě když je jedenácti dělitelný součet dvojic cifer od konce rozděleného zadaného čísla. Příklad: Je-li n = 1 234 567 , je 1 + 23 + 45 + 67 = 136 a dále 1 + 36 = 37 , což není číslo dělitelné jedenácti, proto není dělitelné jedenácti ani číslo 1 234 567. n = .. + 9 901⋅ a7 a6 + 99 ⋅ a5 a4 + a3 a2 ⋅101 + .. − a7 a6 + a5 a4 − a3 a2 + a1a0 , Napíšeme-li
(
)
(
)
můžeme odsud vyslovit kritérium dělitelnosti pouze číslem 101, protože 101 je prvočíslo. Trojčíslí Ze
zápisu
(
)
(
n = ... + 1 001⋅ a8 a7 a6 + a5 a4 a3 ⋅ 999 + ... + a8 a7 a6 + a5 a4 a3 + a2 a1a0
)
plynou
kritéria dělitelnosti všemi děliteli čísla 999, tj. čísly 3, 9, 27, 37, 111, 333 a 999. Za povšimnutí stojí hlavně dělitelnost čísly 27 a 37. plynou Ze zápisu n = ... + 999 ⋅ a8 a7 a6 + a5 a4 a3 ⋅1 001 + ... + a8 a7 a6 − a5 a4 a3 + a2 a1a0
(
)
(
)
kritéria dělitelnosti všemi děliteli čísla 1 001, tj. čísly 7, 11, 13, 77, 143 a 1 001. Za povšimnutí stojí hlavně dělitelnost čísly 7, 11 a 13. Příklad: Je-li n = 1 234 567 , je 1 − 234 + 567 = 334 , což není číslo dělitelné jedenácti, proto není dělitelné jedenácti ani číslo 1 234 567. Úloha: Proveďte stejné úvahy pro poslední čtyřčíslí, pětičíslí atd. E. Dělitelnost určovaná pomocí vhodného násobku daného čísla
Úvahy v tomto oddíle jsou založeny na tvrzení: Číslo n = 10k + a0 , kde k ∈ N0, 0 ≤ a0 ≤ 9 , je dělitelné lichým číslem d různým od pěti, právě když existuje celé číslo m takové, že k + ma0 je číslem d dělitelné. Toto tvrzení dokazovat nebudeme, důkaz ale není složitý, místo toho ukážeme jeho konkrétní aplikace.
Dvojnásobek Jestliže píšeme n = 10k + a0 , k ∈ N0, 0 ≤ a0 ≤ 9 , je 2n = 20k + 2a0 = 19k + ( k + 2a0 ) . Z poslední rovnosti můžeme vyslovit kritérium dělitelnosti devatenácti: Číslo n = 10k + a0 je dělitelné devatenácti, právě když je devatenácti dělitelné číslo k + 2a0 . To platí proto, že čísla 2 a 19 jsou nesoudělná. Příklad: Je-li n = 1 938 , je 193 + 2 ⋅ 8 = 209 a 20 + 2 ⋅ 9 = 38 , což je číslo dělitelné devatenácti, proto je devatenácti dělitelné i číslo 1 938. Kdybychom napsali 2n = 17 k + ( 3k + 2a0 ) , resp. 2n = 15k + ( 5k + 2a0 ) atd., mohli bychom analogicky vyslovit kritérium dělitelnosti sedmnácti, resp. patnácti (ale i třemi, či pěti) atd. Kdybychom napsali 2n = 21k + ( − k + 2a0 ) , resp. 2n = 23k + ( −3k + 2a0 ) atd., mohli bychom analogicky vyslovit kritérium dělitelnosti jednadvaceti (ale i třemi, či sedmi), resp. třiadvaceti atd. Trojnásobek Z rovností
3n = 29k + ( k + 3a0 ) = 28k + ( 2k + 3a0 ) = 27k + ( 3k + 3a0 )
atd.
můžeme
analogicky vyslovit kritéria dělitelnosti devětadvaceti, osmadvaceti (ale i dvěma, sedmi, čtrnácti), sedmadvaceti (ale i třemi, devíti) atd. Z rovností 3n = 31k + ( − k + 3a0 ) = 32k + ( −2k + 3a0 ) = 33k + ( −3k + 3a0 ) atd. můžeme analogicky vyslovit kritéria dělitelnosti jednatřiceti, dvaatřiceti (ale i dvěma, čtyřmi, osmi, šestnácti), třiatřiceti (ale i třemi, jedenácti) atd. Čtyřnásobek Z rovností 4n = 39k + ( k + 4a0 ) = 37k + ( 3k + 4a0 )
atd. můžeme analogicky vyslovit
kritéria dělitelnosti devětatřiceti (ale i třemi, třinácti), sedmatřiceti atd. Z rovností 4n = 41k + ( −k + 4a0 ) = 43k + ( −3k + 4a0 ) atd. můžeme analogicky vyslovit kritéria dělitelnosti jednačtyřiceti, třiačtyřiceti atd. Úloha: Proveďte stejné úvahy pro pětinásobek, šestinásobek atd.
