Az oldal tölt...

Keresés

Legújabb cikkek

Támogató

Fazekas

Szabványok

Valid XHTML 1.0 Strict

Valid CSS!

Szerkesztő
Kategória: Bizonyítás Évfolyam: 9.
Kulcsszó: Elsőfokú diofantikus egyenletek, egyenlőtlenségek Lektorálás: Nem lektorált

Az elsőfokú diofantoszi egyenlet

Elsőfokú diofantoszi egyenlet általános megoldása

a, b, x, y, \in \mathbb{Z}
Az általános elsőfokú diofantoszi egyenletet a következő módon szokás fölírni: ax+by=c (a, b és c paraméter).
A bal oldala nyilvánvalóan osztható (a; b)-val, így ahhoz, hogy az egyenlet megoldható legyen teljesülnie kell a következő feltételnek: (a; b)|c (Később belátjuk, hogy ha ez a feltétel teljesül, akkor mindig megoldható az egyenlet az egész számok körében.) Ha ez teljesül, akkor leosztom (a; b)-val az egyenletet.
a'x+b'y=c'
a'=\frac{a}{(a; b)} \qquad b'=\frac{b}{(a; b)} \qquad c'=\frac{c}{(a; b)}
Az euklideszi algoritmus segítségével keresünk olyan k és l számokat, amelyekre a'k+b'l=1. (Ilyet biztosan találunk, mert (a'; b')=1 és az algoritmus ezen két számot vonja ki addig egymásból - a maradékos osztás lényegében véges sokszor elvégzett kivonás -, amíg megkapjuk a legnagyobb közös osztót, jelen esetben az 1-t.)

Példa

a'=51 \qquad b'=23
Végezzük el erre a két számra az euklideszi algoritmus lépéseit!
\begin{tabular}{llll} (51; 23) & 51=2\cdot 23+5 & \implies & 5=51-2\cdot 23 \\ (23; 5) & 23=4\cdot 5+3 & \implies & 3=23-4\cdot 5 \\ (5; 3) & 5=1\cdot 3+2 & \implies & 2=5-1\cdot 3 \\ (3; 2) & 3=1\cdot 2+1 & \implies & 1=3-1\cdot 2 \\ \end{tabular}
Most a jobb oldali egyenletekből fejezzük ki az 1-et 51 és 23 felhasználásával!
1=3-1\cdot 2=3-1\cdot (5-1\cdot 3)=23-4\cdot 5-1\cdot (5-1\cdot (23-4\cdot 5)=23-4\cdot (51-2\cdot 23)-1\cdot \bigg[(51-2\cdot 23)-1\cdot \Big(23-4\cdot (51-2\cdot 23)\Big)\bigg]=20\cdot 23-9\cdot 51=1
Ebben az esetben k=-9 és l=20 adódott.

Levezetés - folytatás

A már megoldott a'k+b'l=1 egyenletet szorozzuk be c'-vel! Így megkaptuk az a'x+b'y=c' megoldását: x_0=c'k és y_0=c'l. Ezt (a; b)-val szorozva megkapjuk az eredeti, ax+by=c egyenletet és így a megoldásait. Észrevehető, hogy \infty sok megoldás létezik. Ezeket a következő módon képezzük: ( k \in \mathbb{Z} )~~a(x_0+ky)+b(y_0-kx)=c.
Főgombok VisszaElőreFrissítHibát találtál? Jelentsd!NyomtatMutat