Algebra és számelmélet 3

A permutáció fogalma; permutációk szorzása és hatványozása; idegen permutációk felcserélhetősége; felbontás idegen ciklusok szorzatára.

Tananyagok:

• jegyzet (1.1–1.16)
• gyakorlófeladatok (1–4)
• Hartmann Miklós matematika gyakorlóoldala (lásd a Permutációk: ciklusfelbontás és a Permutációk: szorzás című feladatokat)
• Diszkrét matematika 3 tananyagok permutációkról

1. HF

• A feladatsorból az 5–9 feladatok közül egyet kell megoldani.
• Játsszon ezzel a „játékkal”, és figyelje meg, hogy a pontokat mozgatva hogyan változnak a $\rho$ és $A/\rho$ halmazok. A megfigyelt szabályszerűségek alapján találja ki, hogy milyen halmazokat kell írni a kérdőjelek helyére. Ügyeljen a kerek és kapcsos zárójelek megfelelő használatára.
  1. Ha $\rho=\big\{(a,a),(b,b),(c,c),(d,d),(e,e),(a,c),(c,a),(b,e),(e,b)\big\}$, akkor $A/\rho = ?$
  2. Ha $\rho=\big\{(a,a),(b,b),(c,c),(d,d),(e,e),(a,e),(e,a),(b,c),(c,b),(b,d),(d,b),(c,d),(d,c)\big\}$, akkor $A/\rho = ?$
  3. Ha $A/\rho = \big\{ \{a,c\}, \{b\}, \{d\}, \{e\} \big\}$, akkor $\rho=?$
  4. Ha $A/\rho = \big\{ \{a,b,c\}, \{d\}, \{e\} \big\}$, akkor $\rho=?$

Permutáció inverziói; páros és páratlan permutációk; a szimmetrikus és az alternáló csoport; felbontás transzpozíciók szorzatára; a páros és páratlan permutációk száma. Ekvivalenciarelációk és osztályozások; leképezés magja.

Tananyagok:

• jegyzet (1.17–2.12)
• gyakorlófeladatok (10–14)
• permutációs játékok: cserebere transzpozíciókkal, cserebere hármas ciklusokkal, tizenötös játék
• 15-ös játék, a tili-toli rejtélye (Torma Bence prezije)
• „tökéletes” kártyakeverés
• Hartmann Miklós matematika gyakorlóoldala (lásd az Osztályozások című feladatot)
• Diszkrét matematika 1 tananyagok relációkról: előadás, gyakorlat

2. HF

• A feladatsorból a 15–18 feladatok közül egyet kell megoldani.
• Játsszon a „kivonós” játékkal, és írja le a megfigyeléseit. Néhány kérdés, amire érdemes lehet fókuszálni: Milyen számok kerülnek fel a táblára? Melyik a legkisebb szám, ami fel lesz írva a táblára? Hány szám kerül fel a táblára? Melyik játékosnak van nyerő stratégiája, és mi az? (Persze a válaszok mindig az előre felírt két számtól függnek.)

A megoldásokat a következő órán (szeptember 22) kell beadni.

Ekvivalenciák és osztályozások kapcsolata. Részbenrendezett halmazok; fedési reláció és Hasse-diagram; minimális, maximális, legkisebb és legnagyobb elemek.

Tananyagok:

• jegyzet (2.13–2.31)
• gyakorlófeladatok (19–23)
• Diszkrét matematika 1 tananyagok relációkról: előadás, gyakorlat

3. HF

• A feladatsorból a 24–27 feladatok közül egyet kell megoldani.
• Tudjuk, hogy $4 \cdot 150 - 11 \cdot 54 = 6$. Olvassa le ebből az alábbi egyenletek egy-egy megoldását:
  1. $150x+54y=6$
  2. $150x-54y=12$
  3. $54x-150y=18$
  4. $54x+150y=24$
• A „Permutációk” című elektronikus teszt október 2-áig fut.

A megoldásokat a következő órán (szeptember 29) kell beadni.

Kapcsolat a minimális (maximális) és a legkisebb (legnagyobb) elemek között. A legnagyobb közös osztó fogalma; euklideszi algoritmus; Euklidész lemmája; a kétismeretlenes lineáris diofantoszi egyenlet megoldhatóságának kritériuma és általános megoldása.

Tananyagok:

• jegyzet (2.32–3.16)
• gyakorlófeladatok (28–29) + euklideszi algoritmus
• Hartmann Miklós matematika gyakorlóoldala (lásd a Legnagyobb közös osztó és a Diofantoszi egyenlet című feladatokat)
• Egy nyúl ugrál a számegyenesen vagy egy sokszögön
• Lattice of Factors (Wolfram Demonstrations Project)
• Diszkrét matematika 2 tananyagok számelméletből (lásd az 1. hét anyagát)

4. HF

• A feladatsorból a 30–34 feladatok közül egyet kell megoldani.

A megoldást a következő órán (október 6) kell beadni.

A kétismeretlenes lineáris diofantoszi egyenletekről szóló tétel bizonyítása. A kongruenciareláció definíciója és alapvető tulajdonságai.

Tananyagok:

• jegyzet (3.11, 3.17–3.23)
• gyakorlófeladatok (35)
• Diszkrét matematika 2 tananyagok számelméletből (lásd a 2. hét anyagát)

5. HF

• A feladatsorból a 36–39 feladatok közül egyet kell megoldani.
• Ebben a „játékban” az egész számokat lehet kiszínezni és sorokba tördelni. Kísérletezzen vele, és figyelje meg, hogy a színminta hosszától (jelölje ezt $n$) és a sorok hosszától (jelölje ezt $m$) függően hogyan alakul az ábra. Hány különböző szín lép fel egy oszlopban? (A válasz egyetlen képlettel leírható $n$ és $m$ függvényében, de bármilyen más megfigyelést is be lehet küldeni, bizonyítás, indoklás nélkül is.)

A megoldásokat a következő órán (október 13) kell beadni.

Lineáris kongruencia megoldhatóságának kritériuma és általános megoldása; modulo $m$ multiplikatív inverz; lineáris kongruenciarendszer megoldhatóságának kritériuma és általános megoldása.

Tananyagok:

• jegyzet (3.24–3.36)
• gyakorlófeladatok (40–43)
• illusztráció kongruenciarendszerekhez: sorminta, sorminta automatikus palettával
• Hartmann Miklós matematika gyakorlóoldala (lásd a Lineáris kongruencia című feladatot)
• Diszkrét matematika 2 tananyagok számelméletből (lásd a 2. hét anyagát)

6. HF

• Játsszon ezzel a játékkal, figyelje meg, hogy mi történik a paraméterek változtatásakor, és írja le a megfigyeléseit.

A megoldást CooSpace-en kell beküldeni keddig (október 18).

Lineáris kongruenciarendszerek megoldási módszerei; kínai maradéktétel; kínai bijekció.

Tananyagok:

• jegyzet (3.37–3.38)
• gyakorlófeladatok (44–49)
• piros és kék bogyók (illusztráció kongruenciarendszerekhez és mindenhez (is))
• egy videó a kínai maradéktétel alkalmazásáról a rádiólokációban
• futólépés a tóruszon két dimenzióban és három dimenzióban
• két nyúl ugrál a számegyenesen
• Hartmann Miklós matematika gyakorlóoldala (lásd a Kongruenciarendszer és a Kínai maradéktétel című feladatokat)
• Diszkrét matematika 2 tananyagok számelméletből (lásd a 2. hét anyagát)

7. HF

• A feladatsorból az 50–53 feladatok közül egyet kell megoldani.
• Hány olyan szám van 1-től 7000-ig, ami relatív prím 7000-hez? Útmutatás: Egy szám akkor és csak akkor relatív prím 7000-hez, ha nem osztható se 2-vel, se 5-tel, se 7-tel (miért?). Tehát a választ megkaphatjuk úgy, hogy az $U = \{ 1,2,\dots,7000\}$ univerzumból kirostáljuk az alábbi három halmaz elemeit a szita-formula segítségével: \begin{align} A_1 &= \{ a \in U : 2 \mid a\}\\ A_2 &= \{ a \in U : 5 \mid a\}\\ A_3 &= \{ a \in U : 7 \mid a\} \end{align} Egy kis segítség található ebben a videóban.

A megoldásokat a következő órán (október 27) kell beadni.

Maradékosztályok; teljes maradékrendszerek; műveletek maradékosztályokkal; multiplikatív inverz; maradékosztály-gyűrűk és maradékosztálytestek.

Tananyagok:

• jegyzet (3.39–3.56)
• gyakorlófeladatok (54–55)
• gondolatolvasás
• Hartmann Miklós matematika gyakorlóoldala (lásd a Számolás Z_n-ben című feladatot)
• Diszkrét matematika 2 tananyagok számelméletből (lásd az 5. hét anyagát)

8. HF

• A feladatsorból az 56–58 feladatok közül egyet kell megoldani.
• Mit ad 2022-vel osztva 2021! maradékul? És mit ad 625-tel osztva 624! maradékul? Útmutatás: többet ésszel, mint erővel!

A megoldásokat a következő órán (november 3) kell beadni.

Wilson tétele; az Euler-féle $\varphi$ függvény definíciója és képlete; az Euler–Fermat-tétel.

Tananyagok:

• jegyzet (3.57–3.66 és 3.75–3.77)
• gyakorlófeladatok (59–60)
• „kínai” bijekció

9. HF

• A feladatsorból a 61–64 feladatok közül egyet kell megoldani.
• Sorolja fel az $a=14$ szám összes osztóit; legyenek ezek $u_1,\dots,u_k$. Sorolja fel a $b=9$ szám összes osztóit; legyenek ezek $v_1,\dots,v_l$. Írja fel az összes $u_iv_j$ szorzatot. Milyen kapcsolatban vannak ezek a szorzatok $ab$ osztóival? Mi a helyzet, ha az $a=14$, $b=10$ számokkal tesszük ugyanezt?

A megoldásokat a következő órán (november 10) kell beadni.

Primitív egységgyökök száma; redukált maradékrendszerek; az Euler–Fermat-tétel bizonyítása. Számelméleti függvények; nevezetes példák (osztók száma és összege); gyenge multiplikativitás.

Tananyagok:

• jegyzet (3.67–3.74 és 4.1–4.10)
• gyakorlófeladatok (65–68)
• osztók szorzata vs. szorzat osztói

10. HF

• A feladatsorból a 69–72 feladatok közül egyet kell megoldani.
• Gondolatban egyszerűsítsük az alábbi törteket (amennyire csak lehet): $$ \frac{1}{63},\ \frac{2}{63},\ \frac{3}{63}, \ldots, \frac{62}{63},\ \frac{63}{63}.$$ Milyen nevezők fognak fellépni az egyszerűsített törtekben, és melyik hányszor lép fel?

A megoldásokat a következő órán (november 17) kell beadni.

A páros tökéletes számok leírása; Mersenne- és Fermat-prímek; számelméleti függvény összegzési és megfordítási függvénye; Möbius-féle $\mu$ függvény; Möbius-féle inverziós formula.

Tananyagok:

• jegyzet (4.11–4.37)
• Mersenne- és Fermat-prímek
• GIMPS   fermatsearch.org   Landon Curt Noll's prime pages
• az Euler-féle $\varphi$ függvény összegzési függvénye
• Konvolúció, Möbius-féle inverziós formula

11. HF

• Ismételje át a test feletti polinomokkal kapcsolatban a következőket: polinom és polinomfüggvény, oszthatóság, asszociáltság, egységek, legnagyobb közös osztó és legkisebb közös többszörös, maradékos osztás, euklideszi algoritmus. Ezután számítsa ki euklideszi algoritmussal az alábbi $f$ és $g$ polinomok legnagyobb közös osztóját, és adjon meg olyan $u,v \in \mathbb{R}[x]$ polinomokat, amelyekre $fu+gv = \operatorname*{lnko}(f,g)$. $$ f=x^4+x^3+x^2-1, \qquad g=x^3+1 $$ Segít a jegyzetben az 5.17. Példa, ez a videó, valamint Hartmann Miklós matematika gyakorlóoldala (lásd a Polinomok: lnko című feladatot).

A megoldásokat a következő órán (november 24) kell beadni.

Kétismeretlenes lineáris diofantoszi egyenlet, kongruenciareláció, lineáris kongruencia, maradékosztályok test feletti polinomgyűrűben; polinomgyűrű maradékosztályteste; irreducibilis polinomok $\mathbb{Z}_p$ felett.

Tananyagok:

• jegyzet (5.1–5.51)
• gyakorlófeladatok (73–77)
• Irreducibilis polinomok
• Hartmann Miklós matematika gyakorlóoldala (lásd a Polinomok: maradékos osztás, Polinomok: lnko, és a Polinomok: diofantoszi egyenlet című feladatokat, és esetleg ismétlésként a Polinomok: többszörös gyökök című feladatot)
• komplex számos játékok: nevezetes komplex számok, gyökvonás

12. HF

• A feladatsorból a 78–81 feladatok közül egyet kell megoldani.
• Határozza meg a Viète-formulák segítségével (a gyökök kiszámítása nélkül) a $3x^3+6x^2+24x+18$ polinom gyökeinek négyzetösszegét.

A megoldásokat a következő órán (december 1) kell beadni.

Irreducibilis polinomok a racionális számtest felett; Rolle(?)-tétel; Schönemann–Eisenstein-féle irreducibilitási kritérium; Viète-formulák és szimmetrikus polinomok; racionális törtek felbontása elemi törtek összegére; ekvivalenciák a számfogalom felépítésében.

Tananyagok:

• jegyzet (5.52–5.92)
• gyakorlófeladatok (82–89)
• Irreducibilis polinomok $\mathbb{Q}$ felett
• Szimmetrikus polinomok
• Elemi törtekre bontás
• Ekvivalenciarelációk a számfogalom felépítésében
• The Beauty of Roots

A prímszámok eloszlásával kapcsolatos tételek; Fermat-féle kétnégyzetszám-tétel; Waring-problémakör; pitagoraszi számhármasok.

Tananyagok:

• jegyzet (6.1–6.28)
• Nevezetes számelméleti problémák
• a prímszámok eloszlása (cdf)
• Distribution of the Last Digit of the Primes (Wolfram Demonstrations Project)
• Körmendi Kristóf: A Dirichlet-tétel (szakdolgozat, SZTE, 2009)
• Szabó Lilla: A prímszámtétel bizonyításának története (szakdolgozat, SZTE, 2014)
• Fazekas Róbert: A Waring-sejtés bizonyítása (szakdolgozat, SZTE, 2015)
• Titkosírások