Az oldal tölt...

Keresés

Legújabb cikkek

Támogató

Fazekas

Szabványok

Valid XHTML 1.0 Strict

Valid CSS!

Szerkesztő
Kategória: Bizonyítás - Definíció Évfolyam: 9.
Kulcsszó: Euklideszi algoritmus Lektorálás: Nem lektorált

Az euklideszi algoritmus

Az euklideszi algoritmus helyességének levezetése

a, b, d, r_{i}, m_{i} \in \mathbb{Z} \qquad \ageq b>0
Az a számhoz található olyan r_{1} és m_{1} (nevezetesen az a-nak a b-vel való maradékos osztásának eredménye és maradéka), amelyekre a következő feltételek teljesülnek:
a=r_{1}b+m_{1} \qquad 0\le m_{1}<b
Ha két számnak van egy közös osztója, akkor ezzel a számmal a két szám különbsége is osztható lesz. Így (a; b)=(b; a-r_{1}b)=(b; m_{1})
Hasonlóan a b számhoz is található olyan r_{2} és m_{2}, amelyekre a következő feltételek teljesülnek:
b=r_{2}m_{1}+m_{2} \qquad 0\le m_{2}<m_1
(b; m_{1})=(m_{1}; m_{2})=(a; b)
m_{i-2}=r_{i}m_{i-1}+m_{i} \qquad 0\le m_{i}
Ezt a folyamatot addig folytatjuk, amíg (m_{i}=0). (Mivel a maradékok minden lépés után csökkennek, ezért egy idő után lesz egy ilyen állapot.)
Így (a; b)=(m_{i-1}; m_{i}). De mivel m_{i}=0, így (a; b)=(m_{i-1}; 0)=m_{i-1}
Így megkaptuk a és b számpár legnagyobb közös osztóját.

Következmény

Van olyan k és l egész szám, hogy ka+lb=(a;b)
a és b ugyanis felírható ilyen alakban, és így sorra minden m_j is, mert az m_j-t két ilyen alakban felírható szám különbségeként kapjuk.

Példa

\begin{tabular}{ll}
   (72; 33) & 72=2\cdot 33+6\\
   (33; 6) & 33=5\cdot 6+\boldsymbol{3}\\
   (6; 3) & 6=2\cdot 3+0\\
   (72; 33)=3 \\
\end{tabular}
Főgombok VisszaElőreFrissítHibát találtál? Jelentsd!NyomtatMutat