Kihagyás

1. előadás

Trolling

amogus maximus

amogus prime

Optimum pride eheheh

thats gay

Bevezetés

Contact:

Email: merai@inf.elte.hu

Weboldal

Az előadások fel lesznek töltve a Canvasra. (cAnVaS go brrrrr)

2+2+2: 2 óra előadás, 2 óra gyakorlat, 2 óra egyéni készülés

Jelenlétet canvas-on ellenőrzik, kvízzel. Vizsgába nem számít bele. Az ADOTT óra anyagából.

Félév végén vizsga:

  • írásbeli
    • beugró: 40 (megadott) kérdésből választ 5-öt, ezek lesznek a vizsgán, amiből 4-et kell tudni
    • reguláris
  • szóbeli
    • kötelező :)

Megajánlott jegy nincs.

Számelmélet

Egész számokkal foglalkozik

Példa

\(\frac{a}{b + c} + \frac{b}{a + c} + \frac{c}{a + b} = 4\)

  • végtelen sok megoldás
  • legkisebb megoldás:
    • a = 154476802108746166441951315019919... (nem volt fent elég ideig)
    • b = don't even Bother 36875131794129999827197811565225474825...
    • c = stands for Cope

fő alkalmazásai:

  • kriptográfia
  • kódelmélet, hibajavító kódok

Oszthatóság

Az \(a\) egész osztja a \(b\) egészet: \(a | b\), ha létezik olyan \(c\) egész, mellyel \(a \cdot c = b\) (azaz \(a \neq 0\) esetén \(\frac ba \in \Z\))

Ez egy részbenrendezés. :)))))))))

Amogus

oszthatóság tulajdonságai, mindenki ismeri right? kiegészítő anyagban van

  • tranzitív
  • antiszimmetrikus
  • reflexív

Maradékos osztás tétel

Tetszőleges \(a, b \neq 0\) egész számokhoz egyértelműen létezik \(q, \; r\) egészek, hogy \(a = b \cdot q + r \quad\) és \(\quad 0 \ge r < |b|\)

\(q\): kvóciens

\(r\): maradék

Tétel bizonyítása

Csak nemnegatív számok esetén bizonyítjuk.

  1. Létezés: \(a\) szerinti indukcióval

    • Ha \(a < b\), akkor \(a = b \cdot 0 + a\) (\(q = 0, r = a\))
    • Ha \(a \ge b\) akkor tegyük fel, hogy \(a\)-nál kisebb számok már felírhatók ilyen alakban. Legyen \(a - b = b \cdot q^* + r^*\). Ekkor \(a = b\cdot(q^*+1)+r^*\) és legyen \(q = q^* + 1\), \(r=r^*\)

  2. Egyértelműség: Legyen \(a = b \cdot q + r = b \cdot q^* + r^*\) Ekkor \(b(q-q^*) =\) Ez csak akkor lehet, ha \(q = q^*\) és \(r = r^*\)

Jelölés: r = a mod q q = [a/b] ha a,b > 0

Például:

  • 123 mod 10 = 3
  • 123 mod 100 = 23
  • 123 mod 1000 = 123
  • 123 mod -10 = 3
  • -123 mod 10 = 7

Legnagyobb közös osztó (LNKO)

Definíció

Legyenek \(a, b \in \Z\). A \(d\) nem negatív egész szám az \(a\) és \(b\) legnagyobb köszös osztója ha

  • \(d | a\) és \(d | b\)
  • minden \(k \in \Z\) esetén \(k | a, k | b\), akkor \(k | d\)

Jelölése: \(d = (a,b) = lnko(a,b) = gcd(a,b)\) Definíció szerint \((0,0) = 0\)

Tétel

A legnagyobb közös osztó létezésének tétele.

Figyeljük meg az oszthatósági hálót! A gráf egy része "közös" az \(a\) és \(b\) számokkal. Ennek a részgráfnak a legnagyobb eleme a LNKO. Mivel legnagyobb eleme mindig lesz, ezért LNKO is mindig lesz.

Euklidészi algoritmus

\((a,b) \neq (0,0)\)

Végezzük el a következő osztásokat:

\[ a = bq_1 + r_1, \quad 0 < r_1 < |b| \]
\[ b = r_1q_2 + r_2, \quad 0 < r_2 < r_1 \]
\[ r_1 = r_2q_3 + r_3, \quad 0 < r_3 < r_2 \]
\[ \cdots \]
\[ r_{n-2} = r_{n-1}q_n + r_n, \quad 0 < r_n < r_{n-1} \]
\[ r_{n-1} = r_{n}q_{n+1} \]

Ekkor az LNKO az utolsó nem-nulla maradék: \((a,b) = r_n\)

Itt \(a=r_{-1}, b=r_0\)

Példa 1

\[ (12, 18) = ? \]
\[ 18=1\cdot12+6 \]
\[ 12=2\cdot6 \]

Tehát \((12,18)=6\)

Példa 2

\((351,123) = ?\)

\[ 351 = 2 \cdot 123 + 105 \]
\[ 123 = 1 \cdot 105 + 18 \]
\[ 105 = 6 \cdot 18 + 15 \]
\[ 18 = 1 \cdot 15 + 3 \]
\[ 15 = 5 \cdot 3 \]

Utolsó nem nulla maradék a 3: \((351, 123)=3\)

Bizonyítás: Euklidészi algoritmus

  • Az algoritmus véges sok lépésben véget ér, hiszen a maradékok szig.mon.csök.
  • \(r_n\) közös osztó:
    • \(r_n | r_{n-1} \Rightarrow r_n|r_{n-1}q_n+r_n = r_{n-2}\) .......
    • \(r_n\) legnagyobb közös osztó: \(c | a, c | b \Rightarrow c | r_1 \Rightarrow c | r_2 \Rightarrow \dots \Rightarrow c | r_n\)

Fun facts: Euklidészi algoritmus

(Rekurzívan)

Legyen \(a \neq 0\)

  • Ha \(b = 0\) akkor \((a,b) = a\)
  • Ha \(b \neq 0\) akkor \((a,b) = (|b|, a mod |b|)\)

Az euklidészi algoritmus hatékony.

  • Futási idő \(\approx\) \(2log\,a\) (|b| < a)
  • Bizonyítás \(r_i < \frac 12 r_{i-2}\)

Diofantikus egyenletek

Forráskód

Tipikus példa: Hogyan mérünk ki 3 dl, ha csak 5 és 7 dl-es korsónk van?

(Rendelkezésünkre áll további tetszőleges mennyiségű és nagyságú további tárolóedény is)

Általánosítva: Adott egy két pozitív egész szám \(a,b\). Milyen további számok írhatók fel

\[ ax+by,\; x,y \in \mathbb{Z} \]

alakban?

Lineáris diofantikus egyenlet.

Bővített euklideszi algoritmus

Tétel

Minden \(a,b,c\) egész számok esetén pontosan akkor léteznek \(x,y\) egészek, hogy \(x \cdot a + y \cdot b = c\), ha \((a,b) | c\)

Bizonyítás

Elég \(c = (a,b)\) esetet vizsgálni.

  • Legyenek \(q_i\) \(r_i\) az euklideszi algoritmussal megkapott hányadosok, maradékok: \(r_{i-2} = r_{i-1}q_i+r_i\)
  • Legyenek \(x_{-1} = 1, \; x_0 = 0\) és \(i \ge 1\) esetén legyen \(y_i = y_{i-2} - q_i y_{i-1}\)
  • Hasonlóan legyen \(y_{-1} = 0, y_0 = 1\) és \(i \ge 1\) esetén legyen \(y_i = y_{i-2} - q_i y_{i-1}\)
  • Ekkor \(i \ge 1\) esetén \(x_i a + y_i b = r_i\), speciálisan \(x_n a + y_n b = r_n = (a, b)\)

The actual point

\(x_i = x_{i-2} - q_i \cdot x_{i-1}\)

\(y_i = y_{i-2} - q_i \cdot y_{i-1}\)

  • Leosztom előző két maradékot egymással
  • Megnézem az osztás kvóciensét
  • Behelyettesítek az x-re, y-ra a fönti képlet alapján
  • ???
  • PROFIT