Az euklideszi algoritmus egy formányos módszer két szám legnagyobb közös osztójának kiszámolására.
$a$ és $b$ számokra így néz ki az algoritmus:
\( a = q_1 \cdot b + r_1 \)
\( b = q_2 \cdot r_1 + r_2 \)
\( r_1 = q_3 \cdot r_2 + r_3 \)
\( \vdots \)
\( r_{n-2} = q_n \cdot r_{n-1} + r_n \)
\( r_{n-1} = q_{n+1} \cdot r_n +0 \)
A legnagyobb közös osztó az utolsó nem $0$ maradék ($r_n$).
Az euklideszi algoritmussal továbbá a két szám legnagyobb közös osztója kifejezhető a két szám segítségével:
\( D = \alpha \cdot a + \beta \cdot b \)
Itt $D$ a legnagyobb közös osztó.
Az euklideszi algoritmus egy formányos módszer két szám legnagyobb közös osztójának kiszámolására.
Az Euklideszi algoritmus használatával állapítsuk meg a következő számok legnagyobb közös osztóját.
a) 161 és 119
b) 221 és 299
c) 189 és 161
