V tomto vlákne budem pravidelne dopĺňať, čo sa stihlo prebrať na jednotlivých prednáškach. (Napríklad to môže byť užitočné pre ľudí, ktorí z nejakého dôvodu nemohli prísť na prednášku - aby si mohli pozrieť, čo si treba doštudovať.)
Ak budete mať otázky k niečomu, čo odznelo na prednáškach, otvorte na to nový topic. (Tento topic by som chcel zachovať pre tento jediný účel.)
Prednášky ZS 2021/22 - teória čísel
Moderator: Martin Sleziak
-
Martin Sleziak
- Posts: 5686
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky ZS 2021/22
1. prednáška (23.9.)
Veta o delení so zvyškom. Deliteľnosť. Najväčší spoločný deliteľ, Bézoutova identita, Euklidova lema.
Ako posledné som stihol ukázať dôsledok Euklidovej lemy, ktorý hovorí, že $a\mid c$, $b\mid c$, $(a,b)=1$ $\Rightarrow$ $ab\mid c$. (T.j. ak je číslo deliteľné dvomi nesúdeliteľnými číslami, tak je deliteľné aj ich súčinom.)
Nehovorili sme o tom, ako sa dajú vyrátať čísla spĺňajúce Bézoutovu identitu - ak si potrebujete pripomenúť rozšírený Euklidov algoritmus, nejaké odkazy nájdete tu. Plánujeme sa ale k nemu na tejto prednáške ešte vrátiť (najneskôr pri lineárnych kongruenciách).
Veta o delení so zvyškom. Deliteľnosť. Najväčší spoločný deliteľ, Bézoutova identita, Euklidova lema.
Ako posledné som stihol ukázať dôsledok Euklidovej lemy, ktorý hovorí, že $a\mid c$, $b\mid c$, $(a,b)=1$ $\Rightarrow$ $ab\mid c$. (T.j. ak je číslo deliteľné dvomi nesúdeliteľnými číslami, tak je deliteľné aj ich súčinom.)
Nehovorili sme o tom, ako sa dajú vyrátať čísla spĺňajúce Bézoutovu identitu - ak si potrebujete pripomenúť rozšírený Euklidov algoritmus, nejaké odkazy nájdete tu. Plánujeme sa ale k nemu na tejto prednáške ešte vrátiť (najneskôr pri lineárnych kongruenciách).
-
Martin Sleziak
- Posts: 5686
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky ZS 2021/22 - teória čísel
2. prednáška (30.9.)
Najväčší spoločný deliteľ. Ukázal som, že pre $a=qb+r$ máme $(a,b)=(b,r)$. (Tento vzťah je dôležitý pri rozšírenom Euklidovom algoritme.)
Tiež sme ukázali, že z $(a,b)=1$ a $(a,c)=1$ vyplýva $(a,bc)=1$.
Ďalšie vlastnosti z lemy 2.1.12 sme len povedali bez dôkazu. Prešli sme príklad 2.1.13 o n.s.d $f(n)$ a $f(n+1)$ pre $f(n)=n^4+n^2+1$.
Najmenší spoločný násobok - definícia a vzťah s n.s.d.
Preskočil som lemu 2.1.14 a dôsledok 2.1.15 - vrátime sa k nim neskôr, keď ich budeme potrebovať použiť.
Nehovorili sme o tom, ako sa dajú vyrátať čísla spĺňajúce Bézoutovu identitu - ak si potrebujete pripomenúť rozšírený Euklidov algoritmus, nejaké odkazy nájdete tu. Plánujeme sa ale k nemu na tejto prednáške ešte vrátiť (najneskôr pri lineárnych kongruenciách).
Prvočísla. Definícia, základné vlastnosti, základná veta aritmetiky (jednoznačnosť a existencia rozkladu na prvočísla). Kanonický rozklad, jeho súvis s deliteľnosťou, n.s.d, n.s.n.
Rozloženie prvočísel. Ukázali sme, že v množine prvočísel sú ľubovoľne dlhé medzery.
Plánujeme sa dostať k dôkazu, že rad prevrátených hodnôt prvočísel diverguje. Zatiaľ sme si povedali niečo o číslach bez kvadratických deliteľov, ktoré budeme používať v dôkaze.
Najväčší spoločný deliteľ. Ukázal som, že pre $a=qb+r$ máme $(a,b)=(b,r)$. (Tento vzťah je dôležitý pri rozšírenom Euklidovom algoritme.)
Tiež sme ukázali, že z $(a,b)=1$ a $(a,c)=1$ vyplýva $(a,bc)=1$.
Ďalšie vlastnosti z lemy 2.1.12 sme len povedali bez dôkazu. Prešli sme príklad 2.1.13 o n.s.d $f(n)$ a $f(n+1)$ pre $f(n)=n^4+n^2+1$.
Najmenší spoločný násobok - definícia a vzťah s n.s.d.
Preskočil som lemu 2.1.14 a dôsledok 2.1.15 - vrátime sa k nim neskôr, keď ich budeme potrebovať použiť.
Nehovorili sme o tom, ako sa dajú vyrátať čísla spĺňajúce Bézoutovu identitu - ak si potrebujete pripomenúť rozšírený Euklidov algoritmus, nejaké odkazy nájdete tu. Plánujeme sa ale k nemu na tejto prednáške ešte vrátiť (najneskôr pri lineárnych kongruenciách).
Prvočísla. Definícia, základné vlastnosti, základná veta aritmetiky (jednoznačnosť a existencia rozkladu na prvočísla). Kanonický rozklad, jeho súvis s deliteľnosťou, n.s.d, n.s.n.
Rozloženie prvočísel. Ukázali sme, že v množine prvočísel sú ľubovoľne dlhé medzery.
Plánujeme sa dostať k dôkazu, že rad prevrátených hodnôt prvočísel diverguje. Zatiaľ sme si povedali niečo o číslach bez kvadratických deliteľov, ktoré budeme používať v dôkaze.
-
Martin Sleziak
- Posts: 5686
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky ZS 2021/22 - teória čísel
3. prednáška (7.10.)
Súčet prevrátených hodnôt prvočísel. Ukázali sme si tri dôkazy toho, že rad prevrátených hodnôt prvočísel diverguje.
Povedali sme si tiež niečo o číslach bez kvadratických deliteľov, ktoré sme využívali v dôkaze.
Takisto sme v dôkaze využili to, že rad $\sum\frac1{n^2}$ konverguje. (Čo sa dá ukázať pomerne ľahko.) Ak vás zaujíma dôkaz toho, že presná hodnota tejto sumy je $\pi^2/6$, tak nejaký dôkaz je v texte prednáške (v dodatku) - je to dôkaz pomocou Fourierových radov. Existuje veľa ďalších dôkazov, nejaké odkazy nájdete tu: viewtopic.php?t=65
Jeden z dôkazov, ktorý sme robili (pochádzajúci od Paula Erdősa) sa dá nájsť v Proofs from THE BOOK - trochu som robil tejto knihe reklamu, že je vcelku zaujímavá.
Súčet prevrátených hodnôt prvočísel. Ukázali sme si tri dôkazy toho, že rad prevrátených hodnôt prvočísel diverguje.
Povedali sme si tiež niečo o číslach bez kvadratických deliteľov, ktoré sme využívali v dôkaze.
Takisto sme v dôkaze využili to, že rad $\sum\frac1{n^2}$ konverguje. (Čo sa dá ukázať pomerne ľahko.) Ak vás zaujíma dôkaz toho, že presná hodnota tejto sumy je $\pi^2/6$, tak nejaký dôkaz je v texte prednáške (v dodatku) - je to dôkaz pomocou Fourierových radov. Existuje veľa ďalších dôkazov, nejaké odkazy nájdete tu: viewtopic.php?t=65
Jeden z dôkazov, ktorý sme robili (pochádzajúci od Paula Erdősa) sa dá nájsť v Proofs from THE BOOK - trochu som robil tejto knihe reklamu, že je vcelku zaujímavá.
-
Martin Sleziak
- Posts: 5686
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky ZS 2021/22 - teória čísel
4. prednáška (14.10.)
Prvočíselná funkcia a prvočíselná veta. Sformulovali sme prvočíselnú vetu. Ako príklad jej použitia sme ukázali, že množina $\{p/q; p,q\in\mathbb P\}$ je hustá v $(0,\infty)$. (Nerobil som časť o funkciách $\operatorname{li}(x)$ a $\operatorname{Li}(x)$.)
Prvočíselnú vetu som povedal bez dôkazu. Tu na matfyze sa s jej dôkazom môžete stretnúť napríklad na predmete Vybrané kapitoly z teórie funkcií komplexnej premennej v magisterskom štúdiu.
Čebyševove nerovnosti. Dokázali sme Čebyševove nerovnosti, t.j. $$c_1 \frac x{\ln x} \leq \pi(x) \leq c_2 \frac x{\ln x}.$$ Najprv som chvíľu kecal o tom, že ich síce budeme dokazovať iba pre dostatočne veľké prirodzené čísla - ale že s nejakou námahou navyše by sme to boli schopní rozšíriť na reálne čísla $x\ge2$. (Keďže sa tu nejako vyskytlo to, že funkcia $f(x)=\frac{x}{\ln x}$ je od istého miesta monotónna, tak pridám linku na nejaký príklad, kde táto funkcia tiež hrá úlohu: https://msleziak.com/forum/viewtopic.php?t=1249 - je to otázka o porovnávaní čísel $x^y$ a $y^x$.)
Ukázali sme, že platí $\prod_{p\leq x} p < 4^x,$ a toto sme využili pri dôkaze jednej z nerovností.
Ukázali sme, že pre $d_n=[1,2,\ldots,n]$ platí $d_n\geq 2^{n-2}$. Na základe toho sme vedeli dostať nerovnosť $\pi(n) \geq \frac{n-2}{\lg n}.$
Prvočíselná funkcia a prvočíselná veta. Sformulovali sme prvočíselnú vetu. Ako príklad jej použitia sme ukázali, že množina $\{p/q; p,q\in\mathbb P\}$ je hustá v $(0,\infty)$. (Nerobil som časť o funkciách $\operatorname{li}(x)$ a $\operatorname{Li}(x)$.)
Prvočíselnú vetu som povedal bez dôkazu. Tu na matfyze sa s jej dôkazom môžete stretnúť napríklad na predmete Vybrané kapitoly z teórie funkcií komplexnej premennej v magisterskom štúdiu.
Čebyševove nerovnosti. Dokázali sme Čebyševove nerovnosti, t.j. $$c_1 \frac x{\ln x} \leq \pi(x) \leq c_2 \frac x{\ln x}.$$ Najprv som chvíľu kecal o tom, že ich síce budeme dokazovať iba pre dostatočne veľké prirodzené čísla - ale že s nejakou námahou navyše by sme to boli schopní rozšíriť na reálne čísla $x\ge2$. (Keďže sa tu nejako vyskytlo to, že funkcia $f(x)=\frac{x}{\ln x}$ je od istého miesta monotónna, tak pridám linku na nejaký príklad, kde táto funkcia tiež hrá úlohu: https://msleziak.com/forum/viewtopic.php?t=1249 - je to otázka o porovnávaní čísel $x^y$ a $y^x$.)
Ukázali sme, že platí $\prod_{p\leq x} p < 4^x,$ a toto sme využili pri dôkaze jednej z nerovností.
Ukázali sme, že pre $d_n=[1,2,\ldots,n]$ platí $d_n\geq 2^{n-2}$. Na základe toho sme vedeli dostať nerovnosť $\pi(n) \geq \frac{n-2}{\lg n}.$
-
Martin Sleziak
- Posts: 5686
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky ZS 2021/22 - teória čísel
5. prednáška. (21.10.)
Bertrandov postulát. Dokázali sme Bertrandov postulát. Približne rovnaký dôkaz (s odchýlkami v niektorých detailoch) sa dá nájsť aj na Wikipédii: Proof of Bertrand's postulate.
Bertrandov postulát. Dokázali sme Bertrandov postulát. Približne rovnaký dôkaz (s odchýlkami v niektorých detailoch) sa dá nájsť aj na Wikipédii: Proof of Bertrand's postulate.
-
Martin Sleziak
- Posts: 5686
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky ZS 2021/22 - teória čísel
6. prednáška (28.10.)
Prvočísla špeciálneho tvaru a niektoré otvorené problémy. Povedali sme si niečo o Mersennových a Fermatových číslach. Ako zaujímavosť sme spomenuli aj Gauss-Wantzelovu vetu, ktorá hovorí o skonštruovateľnosti pravidelných $n$-uholníkov pravítkom a kružidlom a súvise s Fermatovými prvočíslami.
V súvislosti s konštrukciami pravítkom a kružidlom som spomenul, že nejaké takéto veci sa dajú odvodiť s použitím rozšírení polí, niečo k tomu je napísané aj tu: viewtopic.php?t=1532
Kongruencie. Stihli sme definíciu a základné vlastnosti kongruencií. (V podstate sme prešli časť 3.1.1 z textu.)
Pri kontrole, že $M_{11}=2^{11}-1$ a $F_5=2^{32}+1$ sú zložené sme spomenuli exponentiation by squaring. (Ak si chcete pozrieť nejakú inú možnosť overenia, že $F_5$ je zložené, pridám takúto linku: To show that Fermat number $F_{5}$ is divisible by $641$.)
Dokázal som aj nutné podmienky pre prvočíselné delitele Mersennových a Fermatových čísiel - tvrdenie 3.1.15 (ak $q\mid 2^p-1$, tak $p\mid q-1$) a vetu 3.1.16 (ak $p\mid 2^{2^m}+1$, tak $p=k2^{m+1}+1$).
Prvočísla špeciálneho tvaru a niektoré otvorené problémy. Povedali sme si niečo o Mersennových a Fermatových číslach. Ako zaujímavosť sme spomenuli aj Gauss-Wantzelovu vetu, ktorá hovorí o skonštruovateľnosti pravidelných $n$-uholníkov pravítkom a kružidlom a súvise s Fermatovými prvočíslami.
V súvislosti s konštrukciami pravítkom a kružidlom som spomenul, že nejaké takéto veci sa dajú odvodiť s použitím rozšírení polí, niečo k tomu je napísané aj tu: viewtopic.php?t=1532
Kongruencie. Stihli sme definíciu a základné vlastnosti kongruencií. (V podstate sme prešli časť 3.1.1 z textu.)
Pri kontrole, že $M_{11}=2^{11}-1$ a $F_5=2^{32}+1$ sú zložené sme spomenuli exponentiation by squaring. (Ak si chcete pozrieť nejakú inú možnosť overenia, že $F_5$ je zložené, pridám takúto linku: To show that Fermat number $F_{5}$ is divisible by $641$.)
Dokázal som aj nutné podmienky pre prvočíselné delitele Mersennových a Fermatových čísiel - tvrdenie 3.1.15 (ak $q\mid 2^p-1$, tak $p\mid q-1$) a vetu 3.1.16 (ak $p\mid 2^{2^m}+1$, tak $p=k2^{m+1}+1$).
-
Martin Sleziak
- Posts: 5686
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky ZS 2021/22 - teória čísel
7. prednáška. (4.11.)
Niečo som povedal o pojme kongruencia v trochu inom, ale veľmi príbuznom, zmysle. Konkrétne o kongruenciách v grupách a okruhoch, ktoré úzko súvisia s normálnymi podgrupami/ideálmi. (Máme vlastne 3 rôzne pohľady, ako sa dá pozerať na normálne podgrupy. Okrem definície sa na ne dá pozerať ako na jadrá homomorfizmov a tiež máme jedno-jednoznačnú korešpondenciu medzi grupami a kongruenciami. Podobne je to s ideálmi v okruhoch a okruhovými kongruenciami.) Toto celé vlastne súvisí s faktorizáciou (faktorovými grupami, okruhmi, a pod.)
Lineárne kongruencie. Veta o tom, kedy existuje riešenie, aký je počet riešení, ako ich nájsť. Vyriešili sme aj jeden konkrétny príklad a na ňom zopakovali aj rozšírený Euklidov algoritmus. (Ukázali sme si aj zápis Euklidovho algoritmu pomocou tabuľky. Dá sa nájsť v poznámkach k prednáške, ale je o ňom niečo aj tu na fóre.)
Čínska veta o zvyškoch. Urobili sme dva dôkazy čínskej vety o zvyškoch a ukázali sme si aj konkrétny príklad.
Niečo som povedal o pojme kongruencia v trochu inom, ale veľmi príbuznom, zmysle. Konkrétne o kongruenciách v grupách a okruhoch, ktoré úzko súvisia s normálnymi podgrupami/ideálmi. (Máme vlastne 3 rôzne pohľady, ako sa dá pozerať na normálne podgrupy. Okrem definície sa na ne dá pozerať ako na jadrá homomorfizmov a tiež máme jedno-jednoznačnú korešpondenciu medzi grupami a kongruenciami. Podobne je to s ideálmi v okruhoch a okruhovými kongruenciami.) Toto celé vlastne súvisí s faktorizáciou (faktorovými grupami, okruhmi, a pod.)
Lineárne kongruencie. Veta o tom, kedy existuje riešenie, aký je počet riešení, ako ich nájsť. Vyriešili sme aj jeden konkrétny príklad a na ňom zopakovali aj rozšírený Euklidov algoritmus. (Ukázali sme si aj zápis Euklidovho algoritmu pomocou tabuľky. Dá sa nájsť v poznámkach k prednáške, ale je o ňom niečo aj tu na fóre.)
Čínska veta o zvyškoch. Urobili sme dva dôkazy čínskej vety o zvyškoch a ukázali sme si aj konkrétny príklad.
-
Martin Sleziak
- Posts: 5686
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky ZS 2021/22 - teória čísel
8. prednáška (11.11.):
Aritmetické funkcie. Multiplikatívne a úplne multiplikatívne funkcie - definícia, základné vlastnosti. Ak $f$ je multiplikatívna, tak aj $g(n)=\sum\limits_{d\mid n} f(d)$ je multiplikatívna. (V dôkaze sme využili lemu 2.1.14, ktorú som pri prednášaní prvej kapitoly preskočil. Zdôvodnil som ju iba pomocou kanonického rozkladu - ak niekedy zvýši čas, tak sa vrátim k dôkazu, ktorý sa neopiera o kanonický rozklad.)
Funkcie $d(n)$ a $\sigma(n)$. Vyjadrenie týchto funkcií z kanonického rozkladu. Charakterizácia párnych dokonalých čísel. (Nerobil som časť o nepárnych dokonalých číslach. Takisto ani to, ako sa $d(n)$ a $\sigma(n)$ funkcie správajú pre veľké $n$.)
Eulerova funkcia. Zadefinovali sme Eulerovu funkciu $\varphi(n)$ a dokázali, že je multiplikatívna.
Aritmetické funkcie. Multiplikatívne a úplne multiplikatívne funkcie - definícia, základné vlastnosti. Ak $f$ je multiplikatívna, tak aj $g(n)=\sum\limits_{d\mid n} f(d)$ je multiplikatívna. (V dôkaze sme využili lemu 2.1.14, ktorú som pri prednášaní prvej kapitoly preskočil. Zdôvodnil som ju iba pomocou kanonického rozkladu - ak niekedy zvýši čas, tak sa vrátim k dôkazu, ktorý sa neopiera o kanonický rozklad.)
Funkcie $d(n)$ a $\sigma(n)$. Vyjadrenie týchto funkcií z kanonického rozkladu. Charakterizácia párnych dokonalých čísel. (Nerobil som časť o nepárnych dokonalých číslach. Takisto ani to, ako sa $d(n)$ a $\sigma(n)$ funkcie správajú pre veľké $n$.)
Eulerova funkcia. Zadefinovali sme Eulerovu funkciu $\varphi(n)$ a dokázali, že je multiplikatívna.
-
Martin Sleziak
- Posts: 5686
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky ZS 2021/22 - teória čísel
9. prednáška (18.11.):
Eulerova funkcia. Vyjadrenie Eulerovej funkcie na základe kanonického rozkladu: $\varphi(n)=\prod_{i=1}^k \left(p_i^{\alpha_i}-p_i^{\alpha_i-1}\right) = n \prod_{p\mid n} \left(1-\frac1p\right)$.
Malá Fermatova veta. Ukázali sme si dva dôkazy malej Fermatovej vety. (Kombinatorický dôkaz a induktívny dôkaz pomocou binomickej vety.) Viacero dôkazov tejto vety je pozbieraných aj na Wikipédii: Proofs of Fermat's little theorem.
Eulerova veta. Urobili sme dva dôkazy Eulerovej vety. (Urobil som dôkaz založený na grupe redukovaných zvyškových tried.)
Ešte Eulerova funkcia. Dokázali sme (dvoma spôsobmi) identitu $n=\sum\limits_{d\mid n}\varphi(d)$.
Lagrangeova veta. Sformulovali sme Lagrangeovu vetu a ukázali, že vlastne vyplýva z toho, čo vieme o počte koreňov polynómu v poli: https://msleziak.com/forum/viewtopic.php?t=1349#p4076
Wilsonova veta. Ukázali sme Wilsonovu vetu - jeden dôkaz bol založený na Lagrangeovej vete, druhý využíval multiplikatívnu grupu poľa $\mathbb Z_p$. (Nerobil som kombinatorický dôkaz.)
Eulerova funkcia. Vyjadrenie Eulerovej funkcie na základe kanonického rozkladu: $\varphi(n)=\prod_{i=1}^k \left(p_i^{\alpha_i}-p_i^{\alpha_i-1}\right) = n \prod_{p\mid n} \left(1-\frac1p\right)$.
Malá Fermatova veta. Ukázali sme si dva dôkazy malej Fermatovej vety. (Kombinatorický dôkaz a induktívny dôkaz pomocou binomickej vety.) Viacero dôkazov tejto vety je pozbieraných aj na Wikipédii: Proofs of Fermat's little theorem.
Eulerova veta. Urobili sme dva dôkazy Eulerovej vety. (Urobil som dôkaz založený na grupe redukovaných zvyškových tried.)
Ešte Eulerova funkcia. Dokázali sme (dvoma spôsobmi) identitu $n=\sum\limits_{d\mid n}\varphi(d)$.
Lagrangeova veta. Sformulovali sme Lagrangeovu vetu a ukázali, že vlastne vyplýva z toho, čo vieme o počte koreňov polynómu v poli: https://msleziak.com/forum/viewtopic.php?t=1349#p4076
Wilsonova veta. Ukázali sme Wilsonovu vetu - jeden dôkaz bol založený na Lagrangeovej vete, druhý využíval multiplikatívnu grupu poľa $\mathbb Z_p$. (Nerobil som kombinatorický dôkaz.)