- Kombinatorika
- Halmazok, rendezett párok, leképezések
- Matematikai logika, ítéletkalkulus
- Gráfelméleti alapok
- Gráfok izomorfiája és síkbarajzolhatósága
- Gráfok bejárása és gráfalgoritmusok
- Kromatikus szám, klikk, perfekt gráfok
- Gráfparaméterek, párosítások
- Hálózatok
- Irányított gráfok, gráfalgoritmusok irányított gráfokban
- Menger tételei, többszörös összefüggőség
- Páros gráfok, párosítások
- Teljes indukció
- Oszthatóság
- Euklideszi algoritmus & Diofantoszi egyenletek
- Kongruenciák
- Mátrixok
- Lineáris egyenletrendszerek
- Determinánsok
- Komplex számok
- Polinomok
- Interpolációs polinomok
- Csoportok, gyűrűk, testek
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$
Prímek
Azokat a számokat, amelyeknek az egységszorzón és önmagukon kívül nincsen más pozitív egész osztója, prímeknek nevezzük.
Ikerprímek
Ha két egymást követő páratlan szám prímszám, akkor azokat ikerprímeknek nevezzük.
A 3-nál nagyobb ikerprímek $6k-1$ és $6k+1$ alakúak, ahol $k \in Z^{+}$.
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.
Prímek (szakszerűen)
Egy $p$ szám prím, ha
$ p \mid ab \Rightarrow p \mid a$ vagy $p \mid b$
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$
Legkisebb közös többszörös (LKKT)
A legkisebb közös többszörös megtalálásának lépései:
- Elkészítjük a prímtényezős felbontást
- Vesszük az összes prímet a két prímtényezős felbontásból
- Mindegyik prím a nagyobbik kitevőt kapja.
Négyzetszámok oszthatósági tulajdonságai
Minden négyzetszám 4-gyel osztva nulla, vagy egy maradékot ad.
Minden négyzetszám 3-mal osztva nulla, vagy egy maradékot ad.
Minden négyzetszám 5-tel osztva nulla, vagy egy vagy négy maradékot ad.
Négyzetszámok maradékai
Minden négyzetszám 4-gyel osztva nulla, vagy egy maradékot ad.
Minden négyzetszám 3-mal osztva nulla, vagy egy maradékot ad.
Minden négyzetszám 5-tel osztva nulla, egy vagy négy maradékot ad.
Trükkösebb oszthatóságok
\( a-b \mid a^n-b^n \)
$ a+b \mid a^n + b^n $ ha $n$ páratlan
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) Számoljuk ki a 108 és a 360 legnagyobb közös osztóját.
b) Számoljuk ki a 37 800 és 39 600 számok legnagyobb közös osztóját.
a) Számoljuk ki a 108 és 360 legkisebb közös többszörösét.
b) Számoljuk ki a 37 800 és a 39 600 számok legkisebb közös többszörösét.
a) 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.
b) 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ó.
c) 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.
Itt mindent megtudhatsz az oszthatóságról. Megnézzük, hogy mi az osztó, az osztási maradék, mikor osztható két szám egymással. Aztán jönnek az oszthatósági szabályok, a 2-vel, 3-mal és 4-gyel való oszthatósági szabály. Az nagyon könnyű, hogy egy szám mikor osztható 5-tel, de aztán azt is megnézzük, hogy milyen szabály van a 6-tal, 8-cal, 9-cel és 11-gyel való oszthatóságra. Azt is megnézzük, hogy mit jelent két szám legnagyobb közös osztója, és azt is, hogyan lehet kiszámolni. Kiderül, hogy mik azok a relatív prímek és még sok-sok izgalom.
