Számelmélet

Az egész számok oszthatóságának és asszociáltságának fogalma és tulajdonságai, oszthatósági szabályok.

Tananyagok:

• jegyzet: 1.1-1.8
• feladatsor: 1-5
• Lattice of Factors (Wolfram Demonstrations Project)

1. HF

• (2 pont) A feladatsorból a 6–12. feladatok közül egyet kell megoldani.
• (1 pont) 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ást a következő gyakorlaton kell beadni.

A legnagyobb közös osztó kétféle definíciója, maradékos osztás, euklideszi algoritmus.

Tananyagok:

• jegyzet: 1.9-1.17
• feladatsor: 13
• Euklideszi algoritmus lépésről lépésre
• egy nyúl ugrál egy sokszögön
• The Euclidean Algorithm (Wolfram Demonstrations Project)
• Hartmann Miklós matematika gyakorlóoldala (lásd a Legnagyobb közös osztó című feladatot)

2. HF

• (2 pont) A feladatsorból a 14-18. feladatok közül egyet kell megoldani.

A megoldást a következő gyakorlaton kell beadni.

Relatív prímség, Euklidész lemmája, a legnagyobb közös osztó tulajdonságai, legkisebb közös többszörös, felbonthatatlan számok és prímszámok kapcsolata, a számelmélet alaptétele.

Tananyagok:

• jegyzet: 1.18-1.33
• feladatsor: -

3. HF

• (2 pont) A feladatsorból a 19-22. feladatok közül egyet kell megoldani.
• (1 pont) Bizonyítsa be az 1.23. Tétel (6)-os állítását. A bizonyításban csak a legnagyobb közös osztó definíciójának két pontját (1.9. Definíció) és az oszthatóság alaptulajdonságait (1.2. Tétel) használja, és minden lépésnél jelezze, hogy pontosan mit használ.

A megoldást a következő gyakorlaton kell beadni.

A számelmélet alaptételének különböző megfogalmazásai, lnko és lkkt kiszámítása a prímhatványtényezős felbontásból. A kétismeretlenes lineáris diofantoszi egyenlet megoldhatóságának kritériuma és általános megoldása.

Tananyagok:

• jegyzet: 1.34-2.6
• feladatsor: 23-28
• egy nyúl ugrál a számegyenesen
• videó diofantoszi egyenletekről + a videóban használt összefirkált prezentáció
• Hartmann Miklós matematika gyakorlóoldala (lásd a Diofantoszi egyenlet című feladatot)

4. HF

• (2 pont) A feladatsorból a 29-32. feladatok közül egyet kell megoldani.

A megoldást CooSpace-en kell beküldeni a következő gyakorlat kezdete előtt (március 6-án 10:50-ig).

A kongruenciareláció definíciója és alapvető tulajdonságai. Lineáris kongruencia megoldhatóságának kritériuma és általános megoldása, modulo $m$ multiplikatív inverz.

Tananyagok:

• jegyzet: 2.7-2.20
• feladatsor: 33-38
• videó kongruenciákról + a videóban használt összefirkált prezentáció
• Hartmann Miklós matematika gyakorlóoldala (lásd a Lineáris kongruencia című feladatot)

5. HF

• (2 pont) A feladatsorból a 39-42. feladatok közül egyet kell megoldani.

A megoldást CooSpace-en kell beküldeni a következő gyakorlat kezdete előtt (március 13-án 10:50-ig).

Lineáris kongruenciarendszer megoldhatóságának kritériuma és általános megoldása, kínai maradéktétel.

Tananyagok:

• jegyzet: 2.21-2.28
• feladatsor: 43-49
• két nyúl ugrál a számegyenesen
• illusztráció kongruenciarendszerekhez és a kínai maradéktételhez
• videó kongruenciákról + a videóban használt összefirkált prezentáció
• Hartmann Miklós matematika gyakorlóoldala (lásd a Kongruenciarendszer és a Kínai maradéktétel című feladatokat)

6. HF

• (2 pont) A feladatsorból az 50-53. feladatok közül egyet kell megoldani.

A megoldást a következő gyakorlaton 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: 2.29-2.49
• feladatsor: 54-55
• gondolatolvasás
• Hartmann Miklós matematika gyakorlóoldala (lásd a Számolás Z_n-ben című feladatot)
• a kínai maradéktétel alkalmazásai
• The radar and the Chinese Remainder Theorem (YouTube)
• Radars and the Chinese Remainder Theorem (blog)

7. HF

• (2 pont) A feladatsorból az 56-59. feladatok közül egyet kell megoldani.
• (1 pont) 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ást a következő gyakorlaton kell beadni.

Wilson tétele. Az Euler-féle $\varphi$ függvény definíciója és képlete, a primitív $n$-edik egységgyökök száma.

Tananyagok:

• jegyzet: 2.50-2.58
• feladatsor: -
• $\varphi(360)$ kiszámítása szita-formulával

8. HF

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

A megoldást a következő gyakorlaton kell beadni.

Az Euler-féle $\varphi$ függvény összegzési függvénye, redukált maradékrendszerek. Modulo $m$ rend, az Euler–Fermat-tétel.

Tananyagok:

• jegyzet: 2.59-2.73
• feladatsor: 64-69

9. HF

• (2 pont) A feladatsorból a 70-75. feladatok közül egyet kell megoldani.

A megoldást a következő gyakorlaton kell beadni.

A primitív gyök fogalma, létezésének szükséges és elegendő feltétele, az indexek fogalma és tulajdonságai, indextáblázat, hatványmaradékok jellemzése az indexszel. Négyzetes maradékok, Legendre-szimbólum. Számelméleti függvények, képlet az osztók számára és az osztók összegére.

Tananyagok:

• jegyzet: 2.74-3.8
• feladatsor: 76-80

10. HF

• (2 pont) A feladatsorból a 81-83. feladatok közül egyet kell megoldani.
• (1 pont) 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ást a következő gyakorlaton kell beadni.

Gyengén multiplikatív számelméleti függvények, $\tau$, $\sigma$ és $\varphi$ gyenge multiplikativitása. A páros tökéletes számok leírása, Mersenne- és Fermat-prímek. Végtelen sok ($4k-1$ alakú) prím létezése, Dirichlet tétele a számtani sorozatokban előforduló prímekről.

Tananyagok:

• jegyzet: 3.9-4.4
• osztók szorzata vs. szorzat osztói (cdf)
• „kínai” bijekció két dimenzióban és három dimenzióban
• Mersenne- és Fermat-prímek
• GIMPS   fermatsearch.org   Landon Curt Noll's prime pages
• Körmendi Kristóf: A Dirichlet-tétel (szakdolgozat, SZTE, 2009)
• Distribution of the Last Digit of the Primes (Wolfram Demonstrations Project)

Kis és nagy hézagok a prímek között, Csebisev tétele, ikerprímek, becslés az $n$-edik prímszámra, prímszámtétel. Pitagoraszi számhármasok, Fermat-féle kétnégyzetszám-tétel, Waring-problémakör. Nyilvános kulcsú titkosírások.

Tananyagok:

• jegyzet: 4.5-4.28
• Nevezetes számelméleti problémák
• a prímszámok eloszlása (cdf)
• 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

11. HF

• (2 pont) A feladatsorból a 11, 18, 75. feladatok közül egyet kell megoldani.

A megoldást a következő gyakorlaton kell beadni.