14. Oszthatóság

Question 1

Oszthatóság

Answer 1

Azt mondjuk, hogy $a$ osztója $b$-nek, vagy más szóval $b$ osztható $a$-val, ha létezik olyan $x∈ \Z$, hogy $b=ax$. Jele: $a|b$.

Question 2

Prím számok:

Answer 2

Prím számok:
A $p>1$ egész számot prímszámnak vagy prímnek nevezzük, ha irreducibilis (felbonthatat lan), azaz nem írható fel $p=xy, x,y>1$ alakban (önmagán és az 1-en kívül nincs közös osztója). Ha p prím és $p|ab$, akkor vagy $p|a$ vagy $p|b$ (prímtulajdonság). Pozitív prím számok halmazát $P$-vel jelöljük.

Question 3

Elemi állítások:

Answer 3

• Tetszőleges $n,m∈ \N,$ $n,m≥1$ természetes számokra
  $p(n · m) = p(n) ∪ p(m)$,
  $n|m↔ p(n) ⊆ p(m)$,
  és n|m esetén
  $p( m n ) = p(m)$$p(n)$.
  (megj.:p(n)-el a prímszámok multihalmazát jelöljük multiplicitással: $p(n)={p_1, …, p_1, p_2, …, p_2, …, p_r}$ pl: $p(12)=2,2,3$).

Question 4

Algoritmikus problémák:

Answer 4

• Legyen az input egy tetszőleges n∈ N természetes szá
  1.) Prímtesztelés probléma: n prímszám-e? (AKS algoritmus, gyors(Agrawal,Kayal,Saxena))
  2.) Prímfelbontás (faktorizálás) probléma: ha n nem prímszám, akkor bontsuk fel legalább két (nála kisebb) szám szorzatára!
  3.) Prímgenerálás probléma: adjunk meg (legalább egy) n-nél nagyobb p prímszá[1]mot!(Végtelen sok prímszám van, biz: vegyük az összes prím szám sorzatát, majd adjunk hozzá 1-et, ekkor egy olyan szám áll elő ami egyik prím számmal sem osztható.)
  A 2. és 3. problémára nem ismert gyors algoritmus, elsőre van.

Question 5

Számelmélet alaptétele:

Answer 5

• Minden $n∈ \Z$, $n \neq 0$ egész szám felbontható (faktorizálható) prímszámok szorzatára, lényegében egyértelműen (azaz csak a tényezők sorrendjében és előjelében lehet eltérés). Minden $n∈ \Z$, $|n|>1$ egész szám felírható $n=p^{α1}_1 ·p^{α2}_2 ·, …, ·p^{αr}_r$ alakban, ahol a $p_i ∈ P$ számok páronként különböző prímszámok, és $α_i ≥1$. Ezt az n számot törzs(vagy prím)tényezős alakjának hívjuk.
• pl.: $n = 84 = 2^2\ ·\ 3\ ·\ 7 \ p_1 = 2,\ \alpha_1 = 2 \ p_2 = 3,\ \alpha_2 = 1 \ p_3 = 7,\ \alpha_3 = 1$

Question 6

LNKO:

Answer 6

• Közös osztó: Azt mondjuk, hogy d közös osztója $a$ és $b$ egész számoknak, ha $d|a$ és $d|b$.
• LNKO: Azt mondjuk, hogy g a legnagyobb közös osztója $a$-nak és $b$-nek, ha g a közös osztók közül a legnagyobb. Jelölése: $lnko(a,b)$ vagy $(a,b)$.

Question 7

LKKT:

Answer 7

• Közös többszörös: A h egész számot a és b egész számok közös többszörösének nevezzük, ha a|h és b|h.
• LKKT: Az a és b számok közös pozitív többszörösei közül a legkisebbet az a és b legkisebb közös többszörösének hívjuk, és lkkt(a,b) vagy [a, b]-vel jelöljük. 12. TÉTEL:
• Tétel: Legyen $a=p^{α1}_1 p^{α2}_2 , …, p^{αr}_r$ és $b=p^{β1}_1 p^{β2}_2 , …, p^{βr}_r$ ahol $0≤ α_i , β_i$ . Ekkor
  1. $lnko(a,b)=p^{min(α1β1)}_1 · p^{min(α2β2)}_2 · … · p^{min(αrβr)}_r$ ,
  2. $lkkt(a,b)=p^{max(α1β1)}_1 · p^{ max(α2β2)}_2 · … · p^{max(αrβr)}_r$ Több számra: $lnko(a,b,…z)=p^{min(α1…ω1)}_1 · … · p^{min(αr…ωr)}_r$
  $lkkt(a,b,…z)=p^{max(α1…ω1)…}_1 · … · p^{max(αr…ωr)}$

Question 8

Relatív prímek:

Answer 8

• Azt mondjuk, hogy a és b relatív prímek, ha $lnko(a,b)=1$.