Euklideszi algoritmus
Euklideszi algoritmus
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ó.
Diofantoszi egyenletek
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 \)
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
Oldjuk meg az alábbi Diofantoszi egyenleteket.
a) \( 13x+8y=17 \)
b) \( 12x+8y=10 \)
c) \( 12x+20y=28 \)
a) Bizonyítsuk be, hogy $a=2n+5$ és $b=2n+3$ relatív prímek bármely $n$ egész számra.
b) Van itt ez a tört:
\( \frac{12n+7}{7n+4} \)
Létezik-e olyan $n$ egész szám, amire ez a tört egyszerűsíthető 5-tel?
