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}$

Kezdés

Cikkek

Extrák

Egyéb

Keresés

Legújabb cikkek

Támogató

Szabványok

Az euklideszi algoritmus