2. előadás

Prím számok

Egy \(\; p \neq 0, \pm 1 \;\) szám prímszám, ha \(p = a \cdot b \Rightarrow p = \pm a\) vagy \(b = \pm b\)

Prímfaktorizáció

Nagy számok prím osztóit megtalálni

Számelmélet alaptétele

Minden szám egyértelműen fekírható pozitív prímek szorzataként (kivétel 0, 1, -1)

Végtelen sok prím van

Euklidész tétele kimondja, hogy végtelen sok prímszám van.

Bizonyítás

Indirekt módon tfh véges sok van. Vegyük csak a 2,3,5 számokat.

Tekintsük a következő számot: \(2 \cdot 3 \cdot 5 + 1 = 31\). (A 31 pírm, de nem prímet ad a képlet általában.)

Ez a szám nem osztható egyetlen prímmel sem (\(2, 3, 5\) közül).

Így az új szám prímtényezős felbontásában kell szerepelnie egy új prímnek.

Prímszámtétel

\(x\)-ig a prímek száma kb. \(\frac{x}{\ln \; x}\)

Osztási maradékok

Kongruenciák

Két számot kongruensnek tekintünk, ha osztási maradékok megegyezik.

\(a \equiv b mod n\) ha \(n | a - b\)

Kongruencia tulajdonságai

• Ekvivalenciareláció
  • Tranzitív: \(a \equiv b mod n\) és \(b \equiv c mod n \; \Rightarrow a \equiv c mod n\)
  • Szimmetrikus
  • Reflexív
• Idenpotencia

Lineáris kongruenciák

Legyenek \(a, b, n \in \Z, \; n > 1\). Ekkor az \(a \cdot x \equiv b mod b\) megoldható a \(\Longleftrightarrow \; (a, n) | b\). Ez esetben pontosan \((a, n)\) darab inkongruens megoldása van \(mod \; n\).