Letný semester 2019/2020
Mail: zaneta.semanisinova na gmail.com
Ak by ste mali otázky alebo potrebovali niečo konzultovať, ozvite sa mi mailom.
Zapísala som do SISu zápočty tým, ktorí získali aspoň 75 bodov za domáce úlohy (ak zápočet nemáte a myslíte si, že by ste ho mali mať, prípadne naopak :), určite sa mi ozvite). Ak nemáte dostatok bodov a chceli by ste zápočet získať, ozvite sa mi mailom.
Od 11.3.2020 je prerušená výuka na MFF až do odvolania. Zadania cvičení k príslušnej látke v skriptách (sledujte stránky prednášky) budem zverejňovať priebežne (približne raz za týždeň). K väčšine úloh budem pridávať aj vzorové riešenia (pravdepodobne písané rukou), ale najprv sa pokúste o vyrátanie príkladov (hlavne tých s !) samostatne (ako na cvičení). Časom budú zverejnené aj ďalšie zadania domácich úloh.
Ak by ste potrebovali pomôcť s úlohami zo zadaní alebo našli v riešeniach chybu, kontaktujte ma mailom. Rovnako ma môžete kontaktovať, ak si nebudete vedieť poradiť s domácou úlohou.
Sledujte prosím tieto stránky, aktuálne informácie sa môžu meniť.
Zápočet bude udelený za domáce úlohy. Zadané budú 4 sady domácich úloh, na každú bude čas 2 týždne. Za sadu sa bude dať získať 25 bodov. Z celkových 100 bodov bude na zápočet potrebných 75 bodov. V prípade, že by sa vám nepodarilo získať dostatočný počet bodov a mali by ste záujem o zápočet, ozvite sa mi mailom a dohodneme sa na nejakých doplňujúcich úlohách.
Domáce úlohy odovzdávajte na začiatku cvičenia alebo pošlite mailom do uvedeného termínu. Posielajte ich vo formáte pdf v jednom súbore, preferovane napísané v LaTeXu. Ak by ste chceli poslať riešenie napísané rukou, použite prosím skener alebo aspoň nejakú šikovnú aplikáciu na fotenie dokumentov, napr. Notebloc PDF scanner.
Fareyho postupnosť, konečné reťazové zlomky. Zadania (úloha č. 1 bola predvedená na tabuli).
Nekonečné reťazové zlomky, zblížené zlomky. Zadania.
Pellove rovnice. Zadania.
Dobré aproximácie, Gaussove celé čísla. Zadania.
Riešenia príkladov sú tento týždeň skeny mojich príprav s doplňujúcimi komentármi, na ďalšie týždne sa posnažím o užívateľsky príjemnejšiu verziu. Ak by ste nevedeli niečo prečítať alebo sa v nich zorientovať, napíšte mi mail.
Riešenia vzorových príkladov (č. -2, -1, 0). Riešenia ostatných príkladov.
Kvadratické rozšírenia celých čísel, diofantické rovnice. Zadania.
Návod na riešenie diofantických rovníc (zhŕňa kroky postupu, pomocou ktorého rovnice riešime a ilustruje ich na príklade č.-2).
Predtým než začnete počítať príklady, odporúčam prezrieť si riešenia vzorových príkladov. Ak by vám niečo nebolo jasné, napíšte mi mail.
Riešenia vzorových príkladov (č. -2, -1, 0). Riešenia ostatných príkladov (a drobné nápovedy k tým s *).
Kontext a časť riešenia príkladu č. 8: text na Wikipédii o tzv. Eisensteinových číslach.
Ak by ste sa chceli dozvedieť viac o riešení diofantických rovníc, môžete si pozrieť diplomku Maroša Hrnčiara (väčšina v nej je samozrejme nad rámec toho, čo používame).
Kvadratické zvyšky, Legendrove symboly, kvadratická reciprocita. Zadania.
V príkladoch sa často používajú tvrdenia a vety zo skrípt (najmä věta 2.4, důsledek 2.5, tvrzení 2.6 a věta 2.12). V riešeniach je na ne väčšinou referencia, ale môže sa stať, že niekde chýba.
Riešenia vzorových príkladov (č. -2, -1, 0). Riešenia ostatných príkladov (a nápovedy k tým s *).
Cyklické grupy a homomorfizmy medzi nimi. Zadania.
Pripomeňte si definície grúp Z_n a (Z_n)^* z algebry. Pozrieť si ich môžete napr. v texte o grupách (prvé dva príklady na strane 3). Ďalej budeme stále používať Lagrangeovu vetu pre rády prvkov v grupe (veta 2.6 - špeciálny prípad, v tom istom texte). V zadaniach je množstvo definícií, ale väčšinu už poznáte z Algebry, zhrnula som ich tam, pretože predpokladám, že ich ešte možno nemáte úplne v pamäti.
Poznatky o cyklických grupách, ktoré budeme potrebovať, by mali byť v zadaniach buď vo forme príkladu alebo spomenuté na začiatku. Ak by vám však chýbala nejaká úvaha alebo kontext, systematicky spísané ich nájdete v texte o grupách v kapitole 4.
K príkladom na homomorfizmy som napísala krátky textík o tom, ako homomorfizmy hľadať (alebo ukázať, že neexistujú).
Ak by vám niečo nebolo jasné, neváhajte sa opýtať.
Riešenia vzorových príkladov (č. -2, -1, 0). Riešenia ostatných príkladov.
Charaktery a Gaussove súčty. Zadania.
Úlohy z tohto cvičenia využívajú poznatky o homomorfizmoch a cyklických grupách, preto určite odporúčam pozrieť si najprv predchádzajúce cvičenie a textík o homomorfizmoch, niektoré úvahy už nebudú v riešeniach popísané tak podrobne. Cvičenia sú tentoraz trochu viac teoretické, ale mali by vám pomôcť s pochopením prednášky.
Riešenia vzorových príkladov (č. -1, 0). Riešenia ostatných príkladov (a nápovedy k tým s *).
Jacobiho symboly a ich aplikácie. Zadania.
Jacobiho symboly zavádzame preto, aby sme pri výpočte predovšetkým Legendrových symbolov, ktoré odpovedajú tomu, či je číslo kvadratický zvyšok modulo prvočíslo, nemuseli rozkladať čísla na prvočísla. Výpočet tak ľahko redukujeme na výpočet Legendrovho/Jacobiho symbolu s malým číslom v "menovateli", ktorý vieme ľahko určiť. Ak by ste sa v tom chceli ešte lepšie zorientovať, pozrite si video Sáry Vyhnalovej z Proseminára z teórie čísel.
V cvičeniach sa používa predovšetkým veta 2.16 zo skrípt, ktorá je sformulovaná aj v zadaniach. Vo vzorových príkladoch sú na jej použitie referencie, v riešeniach ostatných príkladov už referencie nie sú, keďže sa používa pri každej manipulácii s Jacobiho symbolmi. Pre lepšie pochopenie postupov pri riešení kongruencií sa hodí rozmyslieť si príklad 5 (alebo mu uveriť), prípadne si pozrite jeho riešenie. Odporúčam vyriešiť si všetky príklady, nielen tie s !, pretože príklad 5 je poučný a jeho myšlienky používame v predchádzajúcich príkladoch a príklad 6 dopĺňa prednášku.
Riešenia vzorových príkladov (č. -1, 0). Riešenia ostatných príkladov.
Hľadanie primitívnych prvkov a rozklad grúp (Z_n)^* na súčin cyklických grúp. Zadania.
Cvičenia sú zamerané na pochopenie štruktúry multiplikatívnej grupy (Z_n)^* a hľadanie primitívnych prvkov modulo n pomocou nástrojov z prednášky. Je to dôležitá látka, ak by sa vám úlohy nedarilo vyriešiť alebo by ste nerozumeli riešeniam, neváhajte mi napísať mail.
Po vašich podnetoch som napísala ešte vysvetľujúci textík, ktorý zhŕňa najdôležitejšie úvahy a poznatky k tomuto cvičeniu.
Ospravedlňujem sa za škrtanie v riešeniach, píšem rýchlejšie ako myslím.
Riešenia vzorových príkladov (č. -2, -1, 0). Riešenia ostatných príkladov.
Valuácie, riešenie kongruencií pomocou primitívnych prvkov, Carmichaelove čísla. Zadania.
Cvičenie je tento týždeň trochu kratšie, keďže predchádzajúce cvičenie bolo dosť náročné.
Riešenia vzorových príkladov (č. -1, 0). Riešenia ostatných príkladov.
Involúcie, míňanie prvkov, Rabin-Millerov test. Zadania.
V úlohách sa opakovane používajú vlastnosti cyklických grúp (najmä Z_n) - predovšetkým rády prvkov a generovanie podgrúp (pripomeňte si napr. v kapitole 4 v texte o grupách). Ďalej neustále používame Lagrangeovu vetu pre rády prvkov (typicky je v riešeniach referencia, ale už nie podrobné vysvetlenie).
Riešenia sú tento týždeň pomerne dlhé, ale k väčšine príkladov ich zrejme nebudete potrebovať a zvládnete ich sami. K niektorým príkladom sú v rámci zachovania čitateľnosti trochu stručnejšie vysvetlenia. Ak by vám niečo nebolo jasné, určite sa ozvite.
V riešení úlohy 2b) bola chyba, tak som ho (trochu provizórne) opravila.
Riešenia vzorových príkladov (č. -2, -1, 0). Riešenia ostatných príkladov.
Hint k úlohe č. 11: Skúste s použitím najväčších spoločných deliteľov zovšeobecniť úvahy, ktoré sme používali v úlohách č. -1 a 2.
Šifrovanie pomocou RSA, elektronický podpis, rýchle mocnenie, cyklotomické polynómy. Zadania.
Tento týždeň sú cvičenia trochu kratšie, ale venujte pozornosť rozmysleniu toho, prečo RSA a elektronický podpis naozaj fungujú a skúste si sami počítanie s cyklotomickými polynómami predtým, než si pozriete riešenia.
Riešenia vzorových príkladov (č. -1, 0). Riešenia ostatných príkladov.
Špeciálne prípady Dirichletovej vety, Solovay-Strassenov test, prvočísla špeciálnych tvarov. Zadania.
Na tomto cvičení doplníme témy z kapitoly 2.7 v skriptách a pozrieme sa bližšie na Dirichletovu vetu v niektorých špeciálnych prípadoch. Každá úloha je iná, preto cvičenie tentoraz neobsahuje vzorové príklady. Ak by ste si s niektorou úlohou nevedeli poradiť, skúste si najprv pozrieť hint k úlohe a skúsiť ju vyriešiť s ním, až potom si prípadne pozrite riešenie. Samozrejme, ak by niečo nebolo zrozumiteľné, neváhajte mi napísať.
Domáca úloha č. 1, termín odovzdania: štvrtok, 19.3.2020, 17:20
Úloha dopadla vo výsledku veľmi dobre, zopár postrehov k najčastejším chybám v jednotlivých úlohách:
Úloha sa pýtala aj na zblížené zlomky, nielen na reťazový zlomok. Zblížené zlomky sú zlomky od nultého (dolná celá časť) až po posledný (v prípade racionálneho čísla je to to isté číslo).
To, prečo si zvolíte jeden z koreňov kvadratickej rovnice a druhý zahodíte, si zaslúži komentár.
Ak delíte nejakým výrazom, patrí sa skonštatovať, že je nenulový a najlepšie aj napísať prečo.
Bez problémov.
Minimálne riešenie ste našli bez problémov, pozor na to, v akom tvare sú všetky riešenia Pellovej rovnice - musíme uvažovať obe znamienka a celočíselný exponent (pozrite si Tvrzení 1.1).
Domáca úloha č. 2, termín odovzdania: štvrtok, 9.4.2020, 17:20
V riešeniach sa opakovane vyskytovali nejaké menšie chybičky, tu je komentár ku nim:
To, ktoré zblížené zlomky sú dobré aproximácie závisí od desatinnej časti čísla - ak je menšia ako 1/2, tak sú to všetky od nultého po posledný, ak je väčšia, tak sú to všetky od prvého po posledný (bez nultého), pre desatinnú časť 1/2 je to dolná celá časť, horná celá časť a samotný zlomok.
Najčastejšie ste zabúdali na to, že rozklady sú jednoznačné až na asociovanosť, takže nesúdeliteľné činitele naľavo sú s treťou mocninou len asociované. To, že potom sú nejakej tretej mocnine rovné v tomto obore síce platí (pretože jednotky sú len 1 a -1), ale potrebuje to komentár.
Bez problémov.
Zákon kvadratickej reciprocity platí len pre rôzne nepárne prvočísla. Zvyšné prípady (p=2, 17) je nutné rozobrať zvlášť.
Domáca úloha č. 3, termín odovzdania: štvrtok, 7.5.2020, 23:59
Komentár k vašim riešeniam tejto sady úloh:
Vyriešiť úlohu vám nerobilo problém, ale len málokto si uvedomil význam toho, že oproti úlohe v predchádzajúcej sade už poznáme kvadratickú reciprocitu pre Jacobiho symboly, a preto sa môžeme vyhnúť rozkladaniu na prvočísla (ktoré je vo všeobecnosti výpočetne náročné).
Úlohu väčšina z vás vyriešila, ale zväčša ste primitívne prvky buď hádali alebo našli jeden a doplnili k nemu inverz. Skúste sa preto zamyslieť, či by ste sa s úlohou vedeli vysporiadať, keby ste primitívnych prvkov mali nájsť viac alebo efektívne popísať všetky. Vzorové riešenie.
V podstate jediná bežnejšia chyba, ktorá sa ale vyskytla skoro u všetkých, bolo, že ste síce našli nutné podmienky pre obraz 1 pri homomorfizme, ale nevysvetlili ste, prečo touto voľbou homomorfizmus dostaneme. Do textíku o homomorfizmoch pri cvičení 7 som preto pridala všeobecný dôkaz, prečo dostaneme homomorfizmus pri takejto konštrukcii.
Bez problémov.
Bez problémov.
Domáca úloha č. 4, termín odovzdania: štvrtok, 21.5.2020, 23:59
Vzorové riešenia úloh č. 3, 4, 5.
Bez väčších problémov, často ste však zabudli uviesť, prečo musí byť x prvok Z_{11}^*. Riešenia kongruencií typicky uvádzame v celých číslach, takže je vhodné skonštatovať, že váš výsledok je mod 11 (ak to tak je).
Bez problémov.
V úlohe sa vyskytlo dosť veľa chýb alebo zmätočných odôvodnení, je k nej vzorové riešenie (ktoré odporúčam pozrieť si každému z vás). Najčastejšie ste zabúdali prvky x s NSD(x,72)=2 alebo ste neoverili, že prvky, ktoré ste ešte nevylúčili, naozaj míňajú 4.
Bez väčších problémov, ale niektorí z vás úlohu neriešili systematicky - skúste si premyslieť, či by ste vedeli nájsť aj všetkých svedkov pre zadané číslo (a potom si to môžete pozrieť aj vo vzorovom riešení).
Bez problémov (ale na váš podnet je aj k nej vzorové riešenie).