- Kombinatorika
- Gráfelméleti alapok
- Gráfok bejárása és gráfalgoritmusok
- Gráfok izomorfiája és síkbarajzolhatósága
- Irányított gráfok, gráfalgoritmusok irányított gráfokban
- Menger tételei, többszörös összefüggőség
- CPM és PERT algoritmus
- Páros gráfok, párosítások
- Kromatikus szám, klikk, perfekt gráfok
- Gráfparaméterek, párosítások
- Maximális folyam, Ford-Fulkerson-algoritmus
- Mátrixok és vektorok
- Vektorterek, független és összefüggő vektorok
- Lineáris egyenletrendszerek, mátrixok rangja és inverze
- Determináns, sajátérték, sajátvektor
- Lineáris leképezések
- Oszthatóság
- Euklideszi algoritmus & Diofantoszi egyenletek
- Kongruenciák
Oszthatóság
Legnagyobb közös osztó
Az $a$ és $b$ szám legnagyobb közös osztója az a $d$ pozitív szám, amire $ d \mid a$ és $d\mid b$, és e közös osztók közül ez a legnagyobb.
Jelölés: $d=(a,b)$
Néhány oszthatósági szabály
Ha $ a \mid c$ és $ b \mid c$ és $(a,b)=1$ akkor $ab \mid c$
Ha $c \mid ab$ és $(a,c)=1$ akkor $c \mid b$
Számelmélet alaptétele
A nullától és az egységszorzóktól különböző összes $n$ egész szám felbontható prímek szorzatára a sorrendtől és az egységszeresektől eltekintve egyértelműen.
$ n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \dots \cdot p_k^{\alpha_k} $ ahol $k \in Z^{+}$
Itt $k$ a felbontásban szereplő különböző prímek száma.
Felbonthatatlan számok
Egy $q$ szám felbonthatatlan, ha nem létezik olyan egységtől különböző $a$ és $b$ szám, hogy $q=ab$
Prímek (szakszerűen)
Egy $p$ szám prím, ha
$ p \mid ab \Rightarrow p \mid a$ vagy $p \mid b$
Végezzük el az alábbi feladatokat:
a) Az 5728 osztható-e 3-mal?
b) A 4758 osztható-e 3-mal?
c) Az 52742 osztható-e 4-gyel?
d) A 61524 osztható-e 4-gyel?
e) A 3714 osztható-e 6-tal?
f) A 4326 osztható-e 9-cel?
a) Bizonyítsuk be, hogy a 3-nál nagyobb ikerprímszámok összege osztható 12-vel!
b) Melyek azok a \( p \) prímszámok, amelyekre \( 2p-1 \) és \( 2p+1 \) is prím?
a) Igazoljuk, hogy ha egy derékszögű háromszög oldalainak mérőszámai egészek, akkor legalább az egyik befogó mérőszáma páros.
b) Igazoljuk, hogy ha egy derékszögű háromszög oldalainak mérőszámai egészek, akkor az egyik befogó mérőszáma osztható 3-mal.
c) Igazoljuk, hogy ha egy derékszögű háromszög oldalainak mérőszámai egészek, akkor van köztük legalább egy öttel osztható.
d) Igazoljuk, hogy bármely páratlan szám négyzetéből 1-et elvéve 8-cal osztható számot kapunk.
a) Igazoljuk, hogy ha \( n \) páratlan szám, akkor 9 osztója \( 11^n + 7^n \)-nek.
b) Milyen \( n \) természetes szám esetén osztható az alábbi kifejezés 16-tal?
\( 17^n + n\)
c) Igazoljuk, hogy ha \( n \) páratlan, akkor 37 osztója az alábbi kifejezésnek.
\( 1+2^{19} + 3^{19}+4^{19}+\dots + 36^{19} \)
a) Milyen pozitív egész $n$-re lesz a 6 osztója az $1+n^2+n^4+3^n$-nek?
b) Bizonyítsuk be, hogy 7 osztója $333^{444}+444^{333}$-nak.
c) Bizonyítsuk be, hogy 9 osztója $4^n-3n-1$-nek.
a) Bizonyítsuk be, hogy ha egy 5-nél nagyobb prímszám négyzetét 30-cal osztjuk, akkor maradékul 1-et vagy 19-et kapunk.
b) Határozzuk meg a $p, q, r$ prímeket úgy, hogy a $p^4+q^4+r^4-3$ kifejezés értéke szintén prím legyen.
