Kihagyás

Legnagyobb közös osztó

3. Vázolja az euklideszi algoritmust és bizonyítsa be annak helyességét

Tétel: Euklideszi algoritmus helyessége

Minden \(a, b \in \Z\) esetén létezik az \((a, b)\) legnagyobb közös osztó.

Bizonyítás: Euklideszi algoritmus helyessége

A létezés bizonyításához bevezetjük az euklideszi algoritmust. A tétel bizonyítása algoritmikus.

TFH. \((a, b) = (0, 0)\)

Végezzük el a következő osztásokat:
\(1.)\) \(a = b \cdot q_1 + r_1\) \(0 < r_1 < \|b\|\)
\(2.)\) \(b = r_1 \cdot q_2 + r_2\) \(0 < r_2 < r_1\)
\(3.)\) \(r_1 = r_2 \cdot q_3 + r_3\) \(0 < r_3 < r_2\)
\(\dots\) \(\dots\) \(\dots\)
\(n-1.)\) \(r_{n - 2} = r_{n - 1} \cdot q_n + r_n\) \(0 < r_n < r_{n - 1}\)
\(n.)\) \(r_{n - 1} = r_n \cdot q_{n + 1} + 0\)

Ekkor az lnko az utolsó nem 0 maradék: \((a, b) = r_n\)

  • Az algoritmus véges sok lépésben véget ér:
    • \(\;0 < r_n < \dots < r_2 < r_1 < |b|\)
    • Szig. mon. csökken és \(\;> 0\,\) tehát van vége.
  • \(\pink{r_n}\) a közös osztó:
    • \(\; \pink{r_n} \mid r_{n-1} \Longrightarrow \pink{r_n} \mid r_{n-1} \cdot q_n + r_n = r_{n-2} \Longrightarrow \dots \Longrightarrow \pink{r_n} \mid b \Longrightarrow \pink{r_n} \mid a\)
  • \(r_n\) a lnko:
    • \(\green{c} \mid a,\; \green{c} \mid b \Longrightarrow \green{c} \mid r_1 \Longrightarrow \green{c} \mid r_2 \Longrightarrow \dots \Longrightarrow \green{c} \mid r_n\)

4. Mondja ki és bizonyítsa az euklideszi algoritmus futási idejére vonatkozó tételt egész számok körében

Tétel: Euklidészi algoritmus futási ideje

Legyenek \(\,a,\,b \in \Z\,\) és TFH. \(\,1 < |b| < a\). Ekkor az euklidészi algoritmus legfeljebb \(2 \cdot (1 + \log |b|)\) lépésben véget ér.

Bizonyítás: Euklidészi algoritmus futási ideje

TODO

Megmutatjuk, hogy \(\;r_i < \dfrac{1}{2} \cdot r_{i-2}\)

Az algoritmus \(i.\) sora: \(\;r_{i-2} = r_{i-1} \cdot q_i + r_i \quad 0 < r_i < r_{i-1}\)

Itt \(r_i < r_{i-1} \Longrightarrow r_{i-2} = r_{i-1} \cdot q_i + r_i \;>\; r_i \cdot q_i + r_i \;>\; 2 \cdot r_i\)

Ha \(n\) páratlan, akkor \(|b| > r_1 > 2 \cdot r_3 > 4 \cdot r_5 > \dots > 2^{\frac{n-1}{2}} \cdot r_n \Longrightarrow 2^{\frac{n-1}{2}} n < 1 + 2 \log |b|\)