Euklideszi algoritmus & Diofantoszi egyenletek
1. 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
Megnézem, hogyan kell megoldani
2. Oldjuk meg az alábbi Diofantoszi egyenleteket.
a) \( 13x+8y=17 \)
b) \( 12x+8y=10 \)
c) \( 12x+20y=28 \)
Megnézem, hogyan kell megoldani
3.
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?
Megnézem, hogyan kell megoldani
4. Oldjuk meg az alábbi Diofantoszi egyenletet.
\( 24x+39y=10 \)
Megnézem, hogyan kell megoldani
5. Oldjuk meg az alábbi Diofantoszi egyenletet.
\( 10x+4y=12 \)
Megnézem, hogyan kell megoldani
6. Oldjuk meg az alábbi Diofantoszi egyenletet.
\( 26x+10y=12 \)
Megnézem, hogyan kell megoldani
7. Oldjuk meg az alábbi Diofantoszi egyenletet.
\( 8x+6y=16 \)
Megnézem, hogyan kell megoldani
8. Oldjuk meg az alábbi Diofantoszi egyenletet.
\( 46x+26y=154 \)
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 \)
