Univerzita Karlova v Praze Pedagogická fakulta
SEMINÁRNÍ PRÁCE Z OBECNÉ ALGEBRY
DĚLITELNOST CELÝCH ČÍSEL V SOUSTAVÁCH O RŮZNÝCH ZÁKLADECH
2003/2004
Cifrik C.
Dělitelnost celých čísel v soustavách o různých základech Zadání: Najděte pět kritérií pro dělitelnost v jiných soustavách než desítkových. Vypracování:
Opakování důležitých pojmů Dělitelnost v oboru celých čísel V oboru Z pro libovolnou dvojici celých čísel a, b ≠ 0 definujeme: Číslo a je dělitelné číslem b , právě když existuje takové celé číslo k , že platí a = bk , tj. když číslo a je násobkem [ k -násobkem] čísla b . Říkáme pak též, že číslo b je dělitelem čísla a nebo že číslo b dělí číslo a . Píšeme b | a . • číslo k se nazývá podíl čísla a při dělení číslem b • v oboru Z mají čísla a, − a právě tytéž dělitele • čísla 1, − 1, a, − a se nazývají nevlastní [samozřejmí, triviální] dělitelé čísel a, − a v oboru Z ; existují-li další dělitelé čísla a ∈ Z , nazývají se vlastní [nesamozřejmí, netriviální] dělitelé • každé celé číslo je dělitelem nuly, ale nula není dělitelem žádného celého čísla různého od nuly Prvočísla, složená čísla Prvočíslo je každé celé číslo p ( p ≠ 1, p ≠ 0 ), které má jen nevlastní dělitele (někdy se za prvočísla považují jen všechna kladná celá čísla n > 1 , vyhovující uvedeným podmínkám). Každé celé číslo různé od nuly, které má aspoň jednoho vlastního dělitele, se nazývá složené. Čísla 1, − 1 nejsou ani složenými čísly, ani prvočísly. Věta o dělení se zbytkem v oboru celých čísel
∀a, b ∈ Z , b ≠ 0, ∃u , v ∈ Z : (a = bu + v ∧ 0 ≤ v < b )
• číslo u se nazývá částečný [neúplný] podíl čísel a, b (v tomto pořadí) • číslo v se nazývá nejmenší nezáporný zbytek čísla a při dělení číslem b [nejmenší nezáporný zbytek čísla a podle modulu b ], stručně: zbytek při dělení Číselné soustavy Množina určitých znaků s pravidly, která slouží k zobrazení čísel, se nazývá číselná soustava. K zápisu reálných čísel používáme pozičních soustav, u nichž význam znaku závisí na jeho poloze v zápisu a z nichž nejrozšířenější jsou polyadické číselné soustavy.
1
Dělitelnost celých čísel v soustavách o různých základech Polyadické číselné soustavy V z-adické číselné soustavě lze každé přirozené číslo p vyjádřit ve tvaru tzv. z-adického rozvoje n
p = ∑ ai z i = a n z n + a n −1 z n −1 + K + a 2 z 2 + a1 z 1 + a 0 z 0 , i =0
1 , ai ∈ {1, 2, 3, K , z − 1}, a pak zapsat pomocí tzv. z-adického zápisu kde z ∈ N \ {} (α nα n −1 Kα 2α1α 0 )z . Zde z se nazývá základ z-adické číselné soustavy a α i jsou znaky reprezentující čísla ai . Znaky α i (popř. někdy také čísla ai ) se nazývají číslice [cifry]. Index i číslice ai , resp. pozice, která tomuto indexu v číselném obrazu přísluší, se nazývá řád číslice ai , resp. řád obrazu číslice ai . Číslice s indexem i se nazývá číslice řádu i nebo číslice i -tého řádu. Nenulová číslice, která je v číselném obrazu přirozeného čísla p první zleva, se nazývá číslice největšího řádu čísla p . Řád číslice největšího řádu přirozeného čísla p se nazývá řád přirozeného čísla p . Přirozené číslo řádu n − 1 se nazývá n-ciferné. Polyadická soustava se základem dvě se nazývá dvojková [binární, dyadická], se základem tři trojková [ternární], se základem osm osmičková [oktalová], se základem deset desítková [dekadická], se základem šestnáct šestnáctková [hexadecimální] atd.
Kritéria dělitelnosti Veškeré naše další úvahy budou vycházet ze z-adického rozvoje přirozeného čísla p = K a 4 a3 a2 a1a0 , kde a 0 , a1 , a 2 , a3 K jsou cifry, tj. ze zápisu p = K + a 4 z 4 + a3 z 3 + a 2 z 2 + a1 z 1 + a 0 z 0
Výpočty budeme provádět v příslušných z-adických soustavách a čísla budeme zapisovat ve zkráceném z-adickém zápisu bez závorky a indexu označujícího základ, tj. místo (a n a n−1 K a 2 a1 a 0 )z pouze a n a n −1 K a 2 a1 a0 .
Dělitelnost v Z3 Dělitelnost dvěma Pro nalezení kriteria dělitelnosti dvěma v trojkové soustavě použijeme rozklad čísla1 p = K + a 4 10 4 + a3 10 3 + a 2 10 2 + a1101 + a 0 10 0 na p = (K + 1111a 4 + 111a 3 + 11a 2 + a1 ) ⋅ 2 + (K + a 4 + a 3 + a 2 + a1 + a 0 ) . Z tohoto zápisu je patrné, že číslo je dělitelné dvěma, právě když je dvěma dělitelný ciferný součet K + a 4 + a3 + a 2 + a1 + a0 čísla p . 1
Pracujeme v trojkové soustavě, v desítkové soustavě by zápis čísla p vypadal takto:
p = K + a 4 3 4 + a3 33 + a 2 3 2 + a1 31 + a 0 3 0 . Cifra 3 v trojkové soustavě neexistuje. Číslu 3 (tj. základu), odpovídá zápis (10)3 (čteme jedna nula, nikoliv deset). Závorku a index označující základ budeme vynechávat, viz odstavec Kriteria dělitelnosti.
2
Dělitelnost celých čísel v soustavách o různých základech Dělitelnost základem Čísla dělitelná základem končí ve všech z-adických soustavách cifrou 0 . Poznámka: V dalším textu se omezíme na vyšetřování kritérií dělitelnosti čísly menšími než je základ a nebudeme uvažovat dělitelnost číslem 1 .
Dělitelnost v Z4 Dělitelnost dvěma Jelikož p = (K + 2000a 4 + 200a3 + 20a 2 + 2a1 )⋅ 2 + a0 , je číslo p dělitelné dvěma, právě když je dělitelná dvěma cifra a 0 (tj. když číslo p končí 0 nebo 2 ). Dělitelnost třemi Platí p = (K + 1111a 4 + 111a 3 + 11a 2 + a1 )⋅ 3 + (K + a 4 + a3 + a 2 + a1 + a 0 ) . Číslo p je dělitelné třemi, právě když je třemi dělitelný ciferný součet K + a 4 + a 3 + a 2 + a1 + a 0 čísla p .
Dělitelnost v Z5 Dělitelnost dvěma Jelikož p = (K + 2222a 4 + 222a3 + 22a 2 + 2a1 )⋅ 2 + (K + a 4 + a3 + a 2 + a1 + a0 ), je číslo p dělitelné dvěma, právě když je dělitelný dvěma ciferný součet čísla p . Dělitelnost třemi
p = (K + 1313a 4 + 131a3 + 13a 2 + a1 ) ⋅ 3 + (K + a 4 + 2a3 + a 2 + 2a1 + a 0 ) = = (K + 1313a 4 + 132a3 + 13a 2 + 2a1 ) ⋅ 3 + (K + a 4 − a3 + a 2 − a1 + a 0 ) =
= (K + 1314a 4 + 131a3 + 14a 2 + a1 + a 0 ) ⋅ 3 + (K − a 4 + a3 − a 2 + a1 − a 0 ) ⋅ 2
Číslo p je dělitelné třemi, právě když je třemi dělitelný alternovaný ciferný součet čísla p . Dělitelnost čtyřmi Jelikož p = (K + 1111a 4 + 111a3 + 11a 2 + a1 )⋅ 4 + (K + a 4 + a3 + a 2 + a1 + a 0 ) , je číslo p dělitelné čtyřmi, právě když je dělitelný čtyřmi ciferný součet čísla p .
Dělitelnost v Z6 Dělitelnost dvěma Jelikož p = (K + 3000a 4 + 300a3 + 30a 2 + 3a1 )⋅ 2 + a0 , je číslo p dělitelné dvěma, právě když je dělitelná dvěma cifra a 0 (tj. a0 ∈ {0, 2, 4}). Kriterium bychom mohli objevit i takto: Ze zápisu p = (K + 1000a 4 + 100a3 + 10a 2 + a1 )⋅ 10 + a 0 je patrné, že poslední cifra a0 rozhoduje o dělitelnosti čísla p všemi děliteli čísla 10 , tj. čísly 2, 3 a 10 (číslo 1 zde neuvažujeme), neboť číslo (K + 1000a 4 + 100a3 + 10a 2 )⋅ 10 čísly 2, 3 a 10 dělitelné je. Číslo p je dělitelné dvěma, právě když je dělitelná dvěma cifra a 0 . 3
Dělitelnost celých čísel v soustavách o různých základech Dělitelnost třemi Jelikož p = (K + 2000a 4 + 200a3 + 20a 2 + 2a1 )⋅ 3 + a0 , je číslo p dělitelné třemi, právě když je dělitelná třemi cifra a 0 (tj. a0 ∈ {0, 3}). Dělitelnost čtyřmi Jelikož p = (K + 1300a 4 + 130a3 + 13a 2 + a1 )⋅ 4 + 2a1 + a 0 , je číslo p dělitelné čtyřmi, právě když je dělitelné čtyřmi číslo 2a1 + a0 . Jiné kritérium objevíme použitím zápisu p = (K + 100a 4 + 10a3 + a 2 )⋅ 100 + a1a 0 , z něhož je patrné, že poslední dvojčíslí a1 a0 rozhoduje o dělitelnosti čísla p všemi děliteli čísla 100 , tj. čísly 2, 3, 4, 13, 20, 30 a 100 , neboť číslo (K + 100a 4 + 10a3 + a 2 )⋅ 100 čísly 2, 3, 4, 13, 20, 30 a 100 dělitelné je. Proto číslo p je dělitelné čtyřmi, jeli čtyřmi dělitelné poslední dvojčíslí. Dělitelnost pěti Jelikož p = (K + 1111a 4 + 111a 3 + 11a 2 + a1 )⋅ 5 + (K + a 4 + a3 + a 2 + a1 + a0 ) , je číslo p dělitelné čtyřmi, právě když je dělitelný čtyřmi ciferný součet čísla p .
Dělitelnost v Z7 Dělitelnost dvěma Jelikož p = (K + 3333a 4 + 333a3 + 33a 2 + 3a1 )⋅ 2 + (K + a 4 + a3 + a 2 + a1 + a0 ), je číslo p dělitelné dvěma, právě když je dělitelný dvěma ciferný součet čísla p . Dělitelnost třemi Jelikož p = (K + 2222a 4 + 222a3 + 22a 2 + 2a1 )⋅ 3 + (K + a 4 + a3 + a 2 + a1 + a0 ) , je číslo p dělitelné třemi, právě když je dělitelný třemi ciferný součet čísla p . Dělitelnost čtyřmi Jelikož p = (K + 1515a 4 + 152a3 + 15a 2 + 2a1 )⋅ 4 + (K + a 4 − a3 + a 2 − a1 + a 0 ) , je číslo p dělitelné čtyřmi, právě když je čtyřmi dělitelný alternovaný ciferný součet čísla p. Dělitelnost pěti Jelikož
p = (K + 1254125a 7 + 125424a 6 + 12541a5 + 1254a 4 + 125a3 + 12a 2 + a1 ) ⋅ 5 + + (K + 3a 7 + 4a 6 + 2a 5 + a 4 + 3a 3 + 4a 2 + 2a1 + a 0 )
je číslo p dělitelné pěti, právě když je dělitelné pěti číslo K + 3a 7 + 4a 6 + 2a 5 + a 4 + 3a 3 + 4a 2 + 2a1 + a0 čísla p . Úloha. Je-li p = (23562 )7 , je
(1 ⋅ 2 )7 + (3 ⋅ 3)7 + (4 ⋅ 5)7 + (2 ⋅ 6)7 + (1 ⋅ 2)7 = (2)7 + (12)7 + (26 )7 + (15)7 + (2)7 = (63)7 , což je číslo dělitelné pěti a proto je dělitelné pěti i číslo p = (23562 )7 (pokud by nám
4
Dělitelnost celých čísel v soustavách o různých základech nestačilo k určení dělitelnosti pěti číslo (63) 7 , mohli bychom pokračovat: (2 ⋅ 6)7 + (1 ⋅ 3)7 = (15)7 + (3)7 = (21)7 a (2 ⋅ 2)7 + (1 ⋅ 1)7 = (5)7 ). Dělitelnost šesti Jelikož p = (K + 1111a 4 + 111a 3 + 11a 2 + a1 )⋅ 6 + (K + a 4 + a3 + a 2 + a1 + a0 ), je číslo p dělitelné šesti, právě když je dělitelný šesti ciferný součet čísla p . (Poznámka: Číslo šest je číslo složené, porovnejte kritéria dělitelnosti.)
Dělitelnost v Z8 Dělitelnost dvěma Jelikož p = (K + 4000a 4 + 400a3 + 40a 2 + 4a1 )⋅ 2 + a0 , je číslo p dělitelné dvěma, právě když je dělitelná dvěma cifra a 0 (tj. a0 ∈ {0, 2, 4, 6}). Dělitelnost třemi Jelikož p = (K + 2525a 4 + 253a3 + 25a 2 + 3a1 )⋅ 3 + (K + a 4 − a3 + a 2 − a1 + a0 ) , je číslo p dělitelné třemi, právě když je třemi dělitelný alternovaný ciferný součet čísla p . Dělitelnost čtyřmi Jelikož p = (K + 2000a 4 + 200a3 + 20a 2 + 2a1 )⋅ 4 + a0 , je číslo p dělitelné čtyřmi, právě když je dělitelná čtyřmi cifra a 0 (tj. a0 ∈ {0, 4}). Dělitelnost pěti Jelikož
p = (K + 1463146a 7 + 146314a 6 + 14631a 5 + 1463a 4 + 146a3 + 14a 2 + a1 ) ⋅ 5 + + (K + 2a 7 + 4a 6 + 3a 5 + a 4 + 2a3 + 4a 2 + 3a1 + a 0 )
je číslo p dělitelné pěti, právě když je dělitelné pěti číslo K + 2a 7 + 4a 6 + 3a5 + a 4 + 2a3 + 4a 2 + 3a1 + a 0 . Dělitelnost šesti Jelikož
p = (K + 12525a5 + 1253a 4 + 125a 3 + 13a 2 + a1 ) ⋅ 6 + (K + 2a 5 − 2a 4 + 2a 3 − 2a 2 + 2a1 + a 0 ) ,
je číslo p dělitelné šesti, právě když je dělitelný šesti ciferný součet K + 2a 5 − 2a 4 + 2a3 − 2a 2 + 2a1 + a 0 čísla p . (Poznámka: Číslo šest je číslo složené, porovnejte kritéria dělitelnosti.)
Dělitelnost sedmi Jelikož p = (K + 1111a 4 + 111a3 + 11a 2 + a1 )⋅ 7 + (K + a 4 + a3 + a 2 + a1 + a 0 ) , je číslo p dělitelné sedmi, právě když je dělitelný sedmi ciferný součet čísla p .
5
Dělitelnost celých čísel v soustavách o různých základech
Dělitelnost v Z10 (dekadická soustava) p = K + a 4 10 4 + a 3 10 3 + a 2 10 2 + a1101 + a 0 10 0 Tabulka 1: Tabulka zbytků vyjadřujících kritéria dělitelnosti jednotlivými přirozenými čísly:
Dělitelnost čísla K a 4 a3 a 2 a1 a 0
číslem 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Kritérium dělitelnosti a0 K + a 4 + a 3 + a 2 + a1 + a 0 2a1 + a 0 a0 K + 4a 4 + 4a 3 + 4a 2 + 4a1 + a 0 K + 3a 7 + a 6 − 2a5 − 3a 4 − a3 + 2a 2 + 3a1 + a 0 4a 2 + 2a1 + a 0 K + a 4 + a 3 + a 2 + a1 + a 0 a0 K + a 4 − a 3 + a 2 − a1 + a0 K + 4a 4 + 4a3 + 4a 2 − 2a1 + a0 K − 3a 7 + a6 + 4a5 + 3a 4 − a3 − 4a 2 − 3a1 + a 0 K + 2a8 − 4a 7 − 6a6 − 2a5 + 4a 4 + 6a 3 + 2a 2 − 4a1 + a 0 K − 5a 4 − 5a3 − 5a 2 − 5a1 + a 0 8a3 + 4a 2 − 6a1 + a 0 K + 2a10 + 7 a9 − a8 + 5a7 − 8a6 + 6a5 + 4a 4 − 3a 3 − 2a 2 − 7 a1 + a 0 K − 8a 4 − 8a3 − 8a 2 − 8a1 + a 0 K + 9a10 − a9 − 2a8 − 4a 7 − 8a 6 + 3a5 + 6a 4 − 7 a3 + 5a 2 − 9a1 + a 0 10a1 + a0
Úloha. Je-li n = 86415 , je − 3 ⋅ 8 − 1 ⋅ 6 + 2 ⋅ 4 + 3 ⋅ 1 + 1 ⋅ 5 = −14 , což je číslo dělitelné sedmi, a proto je dělitelné sedmi i číslo n = 86415 .
Literatura BARTSCH, H.-J.: Matematické vzorce. Praha, Mladá fronta 2002. ZHOUF, J.: Kriteria dělitelnosti. In: Jak učit matematice žáky ve věku 10 - 15 let, edit.: Hejný, Milan - Hrubý, Dag - Lišková, Hana - Stehlíková, Naďa - Sýkora, Václav, 1. vyd., Litomyšl, JČMF, 2002, s. 145-152, ISBN: 80-7015-840-9, stať ve sborníku z konference
Dodatek V dodatku uvádíme zápis prvních padesáti čísel v soustavách o základu dvě až deset.
6
Dělitelnost celých čísel v soustavách o různých základech Tabulka 2: Tabulka prvních padesáti čísel v příslušné z-adické soustavě
Z2 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 100000 100001 100010 100011 100100 100101 100110 100111 101000 101001 101010 101011 101100 101101 101110 101111 110000 110001 110010
Z3 1 2 10 11 12 20 21 22 100 101 102 110 111 112 120 121 122 200 201 202 210 211 212 220 221 222 1000 1001 1002 1010 1011 1012 1020 1021 1022 1100 1101 1102 1110 1111 1112 1120 1121 1122 1200 1201 1202 1210 1211 1212
Z4 1 2 3 10 11 12 13 20 21 22 23 30 31 32 33 100 101 102 103 110 111 112 113 120 121 122 123 130 131 132 133 200 201 202 203 210 211 212 213 220 221 222 223 230 231 232 233 300 301 302
Z5 1 2 3 4 10 11 12 13 14 20 21 22 23 24 30 31 32 33 34 40 41 42 43 44 100 101 102 103 104 110 111 112 113 114 120 121 122 123 124 130 131 132 133 134 140 141 142 143 144 200
Z6 1 2 3 4 5 10 11 12 13 14 15 20 21 22 23 24 25 30 31 32 33 34 35 40 41 42 43 44 45 50 51 52 53 54 55 100 101 102 103 104 105 110 111 112 113 114 115 120 121 122
Z7 1 2 3 4 5 6 10 11 12 13 14 15 16 20 21 22 23 24 25 26 30 31 32 33 34 35 36 40 41 42 43 44 45 46 50 51 52 53 54 55 56 60 61 62 63 64 65 66 100 101
Z8 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 20 21 22 23 24 25 26 27 30 31 32 33 34 35 36 37 40 41 42 43 44 45 46 47 50 51 52 53 54 55 56 57 60 61 62
Z9 1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 18 20 21 22 23 24 25 26 27 28 30 31 32 33 34 35 36 37 38 40 41 42 43 44 45 46 47 48 50 51 52 53 54 55
Z10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
7
Dělitelnost celých čísel v soustavách o různých základech
Obsah Opakování důležitých pojmů ................................................................................ 1 Dělitelnost v oboru celých čísel ........................................................................ 1 Prvočísla, složená čísla...................................................................................... 1 Věta o dělení se zbytkem v oboru celých čísel ................................................. 1 Číselné soustavy................................................................................................ 1 Polyadické číselné soustavy.............................................................................. 2 Kritéria dělitelnosti................................................................................................ 2 Dělitelnost v Z3 ...................................................................................................... 2 Dělitelnost dvěma.............................................................................................. 2 Dělitelnost základem ......................................................................................... 3 Dělitelnost v Z4 ...................................................................................................... 3 Dělitelnost dvěma.............................................................................................. 3 Dělitelnost třemi................................................................................................ 3 Dělitelnost v Z5 ...................................................................................................... 3 Dělitelnost dvěma.............................................................................................. 3 Dělitelnost třemi................................................................................................ 3 Dělitelnost čtyřmi.............................................................................................. 3 Dělitelnost v Z6 ...................................................................................................... 3 Dělitelnost dvěma.............................................................................................. 3 Dělitelnost třemi................................................................................................ 4 Dělitelnost čtyřmi.............................................................................................. 4 Dělitelnost pěti .................................................................................................. 4 Dělitelnost v Z7 ...................................................................................................... 4 Dělitelnost dvěma.............................................................................................. 4 Dělitelnost třemi................................................................................................ 4 Dělitelnost čtyřmi.............................................................................................. 4 Dělitelnost pěti .................................................................................................. 4 Dělitelnost šesti ................................................................................................. 5 Dělitelnost v Z8 ...................................................................................................... 5 Dělitelnost dvěma.............................................................................................. 5 Dělitelnost třemi................................................................................................ 5 Dělitelnost čtyřmi.............................................................................................. 5 Dělitelnost pěti .................................................................................................. 5 Dělitelnost šesti ................................................................................................. 5 Dělitelnost sedmi............................................................................................... 5 Dělitelnost v Z10 (dekadická soustava).................................................................. 6 Literatura ............................................................................................................... 6 Dodatek ................................................................................................................. 6 Obsah..................................................................................................................... 8
8
