Probraná látka

Tady se každý týden bude objevovat látka, kterou se daný týden máte naučit, a sada příkladů, kterou byste se měli snažit vyřešit. Představu o tom, co teprve přijde, si můžete udělat z loňských stránek; letos to bude velmi podobné. Postupně budu aktualizovat i dokument se vzorovými řešeními vybraných úloh. Hlavně se mě ale v případě nejasností ptejte na hodinách nebo po mailu – klidně i na látku z lekce, kterou jsme měli třeba před třemi týdny!

Domácí úkoly se letos odevzdávají mailem, ideálně sepsané v LaTeXu; k tomu se vám mohou hodit moje rady a šablony. Taky jsem vám přehledně shromáždil informace o zápočtu. Podívejte se na první, druhé a třetí sady DÚ.

Teorie až tolik neprobereme a rozhodně vás z ní nebudu zkoušet. Hlavním zdrojem bude můj výklad na začátku každé hodiny, jehož obsah bude shrnutý v učebním textu, který sem ke každé hodině rovněž vyvěsím. Jako další zdroj lze klidně použít třeba i Wikipedii, a můžete taky sledovat Sářiny materiály pro lehčí paralelku.

Prerekvizity: Stačí znalosti o dělitelnosti a prvočíslech na úrovni střední školy. Pro ty, kteří chtějí mít nějaký zdroj, jsem je shrnul do „nultého“ učebního textu. Kromě vyslovení potřebných definic a tvrzení v něm také naznačuju jejich důkazy. Ty pro vás vůbec nejsou potřeba; sepsal jsem to jen pro případné zájemce. V závěru textu je také vysvětleno, proč jednoznačnost rozkladu na prvočísla není jasná a v jakých situacích obdobné tvrzení neplatí.

1. hodina, 4. 3. 2021: Úvod, otevřené problémy teorie čísel. Kromě organizačních záležitostí jsme si řekli něco málo o známých nevyřešených problémech teorie čísel, a to o Fermatových a Mersennových prvočíslech, prvočíselných dvojčatech a Goldbachově hypotéze. Obsah výkladu jsem stručně sepsal do učebního textu (který je tu ale skutečně jen pro zajímavost; nijak na něj nebudeme navazovat). Ve zbytku hodiny jsme řešili 1. sadu úloh (zde jsou k nim i nápovědy, k několika z nich jsem sepsal i vzorové řešení) a zájemci se mohli podívat i na náročnější sérii úloh z korespondenčního semináře PraSe.

2. hodina, 11. 3. 2021: Eukleidův algoritmus, Bézoutovy koeficienty, největší společný dělitel. Zavedli jsme největšího společného dělitele a nejmenší společný násobek, naučili jsme se NSD(a,b) počítat pomocí Eukleidova algoritmu a dali jsme ho do souvislosti s množinou celočíselných lineárních kombinací čísel a a b. Definovali jsme Bézoutovy koeficienty a naučili jsme se je počítat pomocí rozšířeného Eukleidova algoritmu. Tady máte 2. sadu úloh a příslušné nápovědy; látku z hodiny si můžete zopakovat v učebním textu. Jako obvykle jsem k několika úlohám sepsal i vzorové řešení.

3. hodina, 18. 3. 2021: Kongruence, Malá Fermatova věta. Naučili jsme se používat kongruence, díky čemuž budeme schopní pracovat s dělitelností mechaničtěji a efektivněji; jako příklad jsme si ukázali, jak odvozovat kritéria dělitelnosti danými čísly. Vyslovili jsme Malou Fermatovu větu, která nám umožní snižovat exponenty v kongruencích. Odkazy: 3. sada úloh, nápovědy, učební text. V neděli bylo zveřejněno zadání první sady domácích úkolů.

4. hodina, 25. 3. 2021: Eulerova funkce a Eulerova věta. Definujeme Eulerovu funkci, ukážeme si vzorec na její výpočet a vyslovíme Eulerovu větu, která zobecňuje Malou Fermatovu. Odkazy: 4. sada úloh, nápovědy, učební text.

5. hodina, 1. 4. 2021: Čínská zbytková věta. Vyslovíme Čínskou zbytkovou větu, ukážeme si základní příklady, v nichž je možné ji využít, a vysvětlíme si její souvislost s důkazem Eulerovy věty. Jak vás znám, budete po mně chtít i její důkaz, tak vám ho nejspíš taky předvedu. Odkazy: 5. sada úloh, nápovědy, výsledky, učební text.

6. hodina, 8. 4. 2021: Těžší příklady na ČZV. Budeme se zabývat náročnějšími příklady, které jako jeden z kroků využívají Čínksou zbytkovou větu. Odkazy: 6. sada úloh, nápovědy, vybrané výsledky, učební text, videovzoráky k úlohám 6.9 a 6.10 (doporučuju u nich rychlost 1,25; v úloze 6.9 je na tabuli na druhém řádku drobný „překlep“, kterého si určitě všimnete, hned jak ho napíšu). Také je zveřejněné zadání druhé sady domácích úkolů.

7. hodina, 15. 4. 2021: Kvadratické zbytky. Definujeme kvadratické zbytky, vyřešíme pomocí nich spoustu úloh a dokážeme některé jejich základní vlastnosti. (Pokročilejší teorii kolem kvadratických zbytků, především Legendreovy symboly a kvadratickou reciprocitu, probereme až koncem semestru, předběžně na 12. lekci.) Odkazy: 7. sada úloh, nápovědy, vybrané výsledky, učební text.

8. hodina, 22. 4. 2021: Vydechnutí. Nebudeme probírat novou teorii; předvedu vám řešení některých těžších příkladů a dám vám prostor na vyřešení příkladů, na které vám na předchozích hodinách nezbyl čas. Nezapomeňte se do 20. 4. přihlásit na Náboj! Soutěž proběhne v pátek 23. dubna.

9. hodina, 29. 4. 2021: Diofantické rovnice I: metoda nekonečného sestupu. 9. sada úloh, nápovědy, vybrané výsledky, učební text.

10. hodina, 6. 5. 2021: Diofantické rovnice II: lineární diofantické rovnice, pythagorejské trojice. 10. sada úloh, nápovědy, učební text.

11. hodina, 13. 5. 2021: Počítání modulo prvočíslo, primitivní prvek. Probrali jsme některá specifika počítání modulo prvočíslo, mimo jiné několik úloh využívající toho, že se v takových kongruencích dá dělit. Zavedli jsme pojem řád prvku a primitivní prvek a bez důkazu jsme si řekli, že primitivní prvek modulo prvočíslo vždy existuje. Odkazy: 11. sada úloh, nápovědy, učební text. Také byla zveřejněná třetí sada domácích úloh. Mj. i pro ty, kteří hodinu třeba zmeškali, jsem natočil video k úloze 11.12, které nás k pojmu primitivní prvek přirozeně dovede (součástí videa je i definice a některé základní vlastnosti.)

12. hodina, 20. 5. 2021: Kvadratické zbytky II, kvadratická reciprocita. Probrali jsme pokročilejší teorii kolem kvadratických zbytků, mimo jiné Eulerovo kritérium, značení pomocí Legendreových symbolů a zákon kvadratické reciprocity. Tato lekce byla přidaná nově oproti loňsku. Odkazy: 12. sada úloh, nápovědy, výsledky, učební text.

13. hodina, 27. 5. 2021: Racionální kuželosečky. Vysvětlili jsme si, jak pomocí pěkných geometrických myšlenek vyřešit homogenní diofantické rovnice druhého stupně ve třech proměnných, tedy například x^2 + 2y^2 = z^2. Učební text bylo zbytečné sepisovat, pěkně je to vysvětleno ve Víťově seriálu na stránkách 21–26. (Jde o text psaný pro nadané středoškoláky, takže jsou tam opakovány některé definice, které vám mohou připadat jasné. Ale jinak by pro vás onen text měl být zhruba na té správné úrovni.) Tady k němu máte klasickou sadu úloh a k nim i nápovědy.

14. hodina, 2. 6. 2021: p-valuace, Lifting the exponent Lemma. Zavedli jsme si přirozený pojem p-valuace pro prvočíslo p a hráli jsme si s jedním tvrzením, které se p-valuací týká. 14. sada úloh (včetně znění LTE), nápovědy.

To je všechno; děkuju všem, kteří vydrželi až do konce. Na opravování domácích úkolů pracuju. Když si s některým příkladem z hodiny nebudete vědět rady, napište mi, rád vám dám nápovědu nebo sepíšu vzorové řešení.

Pokud si chcete prolistovat velmi pěkně a stravitelně sepsaný text, jehož obsah se s látkou prosemináře dost shoduje, doporučuju Víťův „seriál“ napsaný pro korespondenční seminář PraSe. O poznání náročnější, ale taky pěkně sepsaný, je seriál Pepy Svobody a Štěpána Šimsy, pokrývající více témat.