Euklideszi algoritmus, Diofantoszi egyenletek

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ó.

A Diofantoszi egyenletek így néznek ki:

\( ax+by=c \)

ahol $a,b,c \in Z$ és $x,y \in Z$

Megoldásukat azzal kezdjük, hogy kiszámoljuk $a$ és $b$ legnagyobb közös osztóját: $D$, és ezzel végig osztjuk az egyenletet, így kapjuk az

\( Ax+By=C \)

egyenletet, ahol $(A,B)=1$.

A második lépés, hogy az euklideszi algoritmus segítségével kifejezzük $A$ és $B$ legnagyobb közös osztóját, ami az 1, így

\( \alpha \cdot A + \beta \cdot B = 1 \)

egyenletet kapunk.

Ezt az egyenletet beszorozva $C$-vel megkapunk egy megoldást:

\( \left( \alpha \cdot C \right) \cdot A + \left( \beta \cdot C \right) \cdot B = C  \)

Az általános megoldásokat a következő alakban kapjuk meg:

\( x = \alpha \cdot C + k\cdot B \)

\( y = \beta \cdot C - k\cdot A \)