Průvodní povídání 1

Teorie čísel

Průvodní povídání je také k dispozici ve formátu pdf.

Milí pikomaťáci,

\def\N{\mathbb{N}}\def\Z{\mathbb{Z}}

Vítáme tě u prvního dílu letošního průvodního povídání! Tentokrát na téma dělitelnosti a diofantických rovnic. Nejprve si zavedeme trochu terminologie:

Přirozenými čísly budeme myslet čísla 1,2,3,\ldots. Množinu všech přirozených čísel budeme značit symbolem \N. Například 3 je prvkem množiny přirozených čísel, píšeme 3\in \N, ale -7 ani 1/7 nejsou prvky množiny přirozených čísel, píšeme -7\notin \N a 1/7\notin \N.

Celými čísly budeme myslet čísla \ldots,-2,-1,0,1,2,\ldots. Množinu všech celých čísel budeme značit symbolem \Z . Například 3\in\Z a -7\in\Z , ale 1/7\notin\Z .

Číslo a dělí číslo b, pokud b/a \in\Z , tedy číslo b lze vydělit číslem a beze zbytku. V takovém případě píšeme a\mid b, v opačném případě a\nmid b. Tedy například 7\mid 21 (protože 21/7 = 3 \in \Z ) a -17\mid 34, ale 5\nmid 21.

Vyzbrojeni arsenálem mocných pojmů, pojďme si nyní něco zajímavého dokázat!

Tvrzení: Pro libovolné a platí, že 1\mid a a a\mid 0.

Důkaz: Abychom dokázali, že 1\mid a, musíme ukázat, že a/1\in\Z . To ale platí, protože když libovolné celé číslo vydělíme jedničkou, nijak se nám nezmění, a tedy zůstane celé. Podobně pro důkaz a\mid 0 musíme ukázat, že 0/a \in \Z . Jenže 0/a je rovno nule, která jistě je celým číslem.

Uvažme nyní nějaká dvě celá čísla a,b, pro která platí a\mid b. Označme si k=b/a. Z definice dělitelnosti je k celé číslo. Vynásobíme-li obě strany rovnice číslem a, dostaneme, že a\cdot k=b. Obecně platí, že a\mid b právě tehdy, když nějaké takové k\in\Z existuje. Například 7\mid 21, protože volbou k=3 dostaneme že 7\cdot 3=21. Naopak 5\nmid 7, protože pak by muselo být k rovno 7/5, což ale není celé číslo.

Úloha: Uvažme a\in\Z libovolné. Najdi k_{1}\in\Z dovědčující, že a\mid 0. Podobně najdi k_{2}\in\Z pro 1\mid a.

Tvrzení: Nechť a,b,c\in\Z jsou taková, že a\mid b a b\mid c. Pak a\mid c.

Důkaz: Jelikož a\mid b, existuje k_{1}\in\Z takové, že a\cdot k_{1}=b. Podobně z b\mid c plyne existence k_{2}\in\Z takového, že b\cdot k_{2}=c. Pak

a\cdot k_{1}\cdot k_{2}=b\cdot k_{2}=c.

Jelikož k_{1}\cdot k_{2}\in\Z , dostáváme a\mid c.

Tedy například když 7\mid 28 a 28\mid 280, pak i 7\mid 280.

Tvrzení (o součtu dělitelností):

Nechť a,b,c\in\Z jsou taková, že a\mid b a a\mid c. Pak a\mid b+c.

Důkaz: Jelikož a\mid b, existuje k_{1}\in\Z takové, že a\cdot k_{1}=b. Podobně a\mid c nám dává k_{2}\in\Z takové, že a\cdot k_{2}=c. Tedy

a\cdot(k_{1}+k_{2})=a\cdot k_{1}+a\cdot k_{2}=b+c.

Pojmenováním k=k_{1}+k_{2} tedy dostáváme, že a\cdot k=b+c. Protože součet celých čísel je celé číslo, dostáváme k\in\Z . Tedy skutečně a\mid b+c.

Například když 3 \mid 9 a 3 \mid 12, pak i 3 \mid 21.

Zkus nyní sám podobně dokázat následující dvě tvrzení.

Tvrzení: Nechť a,b,c\in\Z jsou taková, že a\mid b. Pak a\mid b\cdot c.

Tvrzení (o násobení dělitelností):

Nechť pro a,b,c,d\in\Z platí, že a\mid b a c\mid d. Pak a\cdot c\mid b\cdot d.

O dělitelnosti se dá ukázat i spousta dalších zajímavých věcí. My je však nyní přesuneme k něčemu jinému, a to k modulení. Nejprve si k tomu zaveďme nějaké značení.

Zbytek čísla a po dělení číslem b budeme značit a\bmod b. Tedy například

6 \bmod 3 = 0, 7 \bmod 3 = 1, 7 \bmod 4 = 3, 18 \bmod 7 = 4, -6 \bmod 5 = 4.

Řekneme, že číslo a je kongruentní s číslem b modulo c, pokud c\mid a-b. Neboli pokud dávají a, b po dělení číslem c stejný zbytek. Tuto skutečnost zapisujeme a\equiv b \pmod c. Tedy například 7 \equiv 1 \pmod 3, 3\equiv 8\equiv-12\pmod 5).

Tvrzení (o součtu zbytků):

Nechť pro a,b,c,d,m\in\Z platí, že a\equiv b\pmod m a c\equiv d\pmod m. Potom a+c\equiv b+d\pmod m.

Důkaz: Jelikož a\equiv b\pmod m, musí m\mid a-b. Podobně z c\equiv d\pmod m musí m\mid c-d. Z tvrzení o součtu dělitelností víme

m\mid (a-b)+(c-d)=(a+c)-(b+d).

Tedy a+c\equiv b+d\pmod m, což jsme chtěli dokázat.

Příklad: Víme, že 2\equiv 17\pmod 5) a 0\equiv 10\pmod 5.

Tedy 0+2\equiv10+17\pmod 5.

Definice: Druhou mocninou čísla a, psáno a^{2}, myslíme číslo a vynásobené samo se sebou. Tedy například 5^{2}=5\cdot 5=25.

Úloha: Spočítej 7^{2}.

Příklad: Ukážeme, že 9 \mid 6^{2}. Rozepíšeme si 6^{2} jako (2\cdot 3)\cdot(2\cdot 3) = 4 \cdot 9. Z toho už vidíme, že 9 \mid 4 \cdot 9.

Tvrzení (o násobení zbytků):

Nechť pro a,b,c,d,m\in\Z platí, že a\equiv b\pmod m a c\equiv d\pmod m. Potom a\cdot c\equiv b\cdot d\pmod m.

Důkaz: Jelikož a\equiv b\pmod m, musí m\mid a-b. Tedy existuje k_{1}\in\Z takové, že m\cdot k_{1}=a-b. Podobně z c\equiv d\pmod m musí m\mid c-d. Tedy existuje k_{2}\in\Z takové, že m\cdot k_{2}=c-d. Přepsáním obou rovností dostáváme

a=m\cdot k_{1}+b, c=m\cdot k_{2}+d.

Pak

a\cdot c=(m\cdot k_{1}+b)\cdot(m\cdot k_{2}+d)=m^{2}+m\cdot k_{1}+m\cdot k_{2}+b\cdot d.

Můžeme si povšimnout, že první tři členy tohoto součtu jsou číslem m dělitelné, tedy dávají po dělení tímto číslem zbytek nula:

m^{2}\equiv m\cdot k_{1}\equiv m\cdot k_{2}\equiv 0\pmod m.

Využitím tvrzení o součtu zbytků tedy dostáváme následující:

m^{2}+m\cdot k_{1}+m\cdot k_{2}+b\cdot d\equiv 0+0+0+b\cdot d\pmod m.

Dohromady tedy máme, že a\cdot c\equiv b\cdot d\pmod m, což jsme chtěli.

Příklad: Víme, že 2\equiv 8\pmod 3 a 4\equiv-2\pmod 3.

Tedy 2\cdot 4\equiv 8\cdot (-2)\pmod 3.

Úloha: Urči zbytek 16\cdot18 po dělení číslem 17.

Příklad: Chceme-li spočítat zbytek po dělení nějakého většího čísla, můžeme tvrzení o součtu a součinu zbytků zkombinovat:

11\cdot12\cdot13+14\cdot15\equiv1\cdot2\cdot3+(-1)\cdot0=6+0\equiv1\pmod 5,

neboli 11\cdot12\cdot13+14\cdot15 dává po dělení 15 zbytek 1.

Úloha Urči zbytek 7\cdot15+9\cdot11 po dělení číslem 4.

Úloha: Urči zbytek 18\cdot19\cdot20\cdot21\cdot22+4\cdot5 po dělení číslem 20.

Jelikož je druhá mocnina jen součin dvou (stejných) čísel, můžeme při počítání zbytku po dělení využívat stejná pravidla, jako jsme využívali dříve. Například:

17\cdot46+14^{2}\equiv2\cdot1+(-1)^{2}\equiv 2+1\equiv3\pmod {15},

neboli 17\cdot46+14^{2} dává po dělení 15 zbytek 3.

Úloha: Urči zbytek 7^{2}\cdot15^{2}+9^{2}\cdot11^{2} po dělení číslem 4.

PRO ZVÍDAVÉ

znalosti nebudou potřeba k řešení úloh v sériích Pikomatu.

Definice: Mocnina je opětované vynásobení čísla sebou samým. Uvažme libovolné číslo a a libovolné přirozené číslo n. Pak a na n-tou značí

a^{n}=\underbrace{a\cdots a}_{n\times}.

Například 3^{4}=3\cdot3\cdot3\cdot3=81.

Příklad: Při práci s většími mocninami můžeme triky odvozené v předchozí kapitole využít úplně stejně:

9^{7}\equiv \underbrace{(9\cdots9)}_{7\times}\equiv \underbrace{((-1)\cdots(-1))}_{7\times}\equiv-1\equiv9\pmod {10}.

Neboli 9^{7} dává po dělení deseti zbytek 9.

Úloha: Urči zbytek 15^{15}+34^{34}+4^{4} po dělení číslem 16.

Úloha: Nechť a je libovolné přirozené číslo. Dokaž, že 10^{a}\equiv1\pmod 3.

Na závěr si ukážeme jeden známý trik. Pro začátek si představme, že máme nějaké velké číslo, a chceme vědět jeho zbytek po dělení třemi. Oním velkým číslem buď například 123\,456. Můžeme si povšimnout, že toto číslo si lze zapsat jako

1\cdot 10^{5}+2\cdot10^{4}+3\cdot10^{3}+4\cdot10^{2}+5\cdot10^{1}+6.

Z poslední úlohy víme, že zbytek 10^{a} je pro všechna přirozená a roven jedné. Tedy zbytek celého součtu je roven

1\cdot1+2\cdot1+3\cdot1+4\cdot1+5\cdot1+6\cdot1=1+2+3+4+5+6=21.

Tedy zbytek 123,456 po dělení číslem 3 je stejný, jako zbytek 21 po dělení číslem 3. Jelikož 21\equiv0\pmod 3, je i zbytek čísla 123\,456 po dělení trojkou roven 0.

Úloha: Podobně spočítej zbytek čísla 246\,810 po dělení třemi.

Úloha: Jak je to se zbytkem po dělení číslem 9? Zkus si projít celý postup znova a uvědom si, co se stane, když trojku nahradíme na vhodných místech devítkou. Co nám tedy o dělitelnosti devítkou říká součet cifer daného čísla?