If you're seeing this message, it means we're having trouble loading external resources on our website.

Ha webszűrőt használsz, győződj meg róla, hogy a *.kastatic.org és a *.kasandbox.org nincsenek blokkolva.

Fő tartalom

Az euklideszi algoritmus

Emlékezz vissza! A és B két egész szám legnagyobb közös osztója (LKO) az a legnagyobb egész szám, amivel A is és B is maradék nélkül osztható.
Az euklideszi algoritmus egy gyors technika arra, hogy két szám LKO-ját meghatározzuk.

Az algoritmus

A LKO(A,B) megkeresésének euklideszi algoritmusa a következő:
  • Ha A = 0, akkor LKO(A,B)=B, mivel LKO(0,B)=B, és itt megállunk.  
  • Ha B = 0, akkor LKO(A,B)=A, mivel LKO(A,0)=A, és itt megállunk.  
  • Írd fel A-t maradékos osztás alakban: (A = B⋅Q + R)
  • Keresd meg LKO(B,R)-t az euklideszi algoritmus alapján, felhasználva az LKO(A,B) = LKO(B,R) összefüggést.

Példa:

Keresd meg a 270 és a 192 LKO-ját!
  • A=270, B=192
  • A ≠0
  • B ≠0
  • A maradékos osztás alapján 270/192 = 1, a maradék 78. Más alakban felírva: 270 = 192 · 1 +78
  • Keresd meg LKO(192,78)-at, mivel LKO(270,192)=LKO(192,78).
A=192, B=78
  • A ≠0
  • B ≠0
  • A maradékos osztás alapján 192/78 = 2, a maradék 36. Más alakban felírva:
  • 192 = 78 · 2 + 36
  • Keresd meg LKO(78,36)-t, mivel LKO(192,78)=LKO(78,36).
A=78, B=36
  • A ≠0
  • B ≠0
  • A maradékos osztás alapján 78/36 = 2, a maradék 6. Más alakban felírva:
  • 78 = 36 · 2 + 6
  • Keresd meg LKO(36,6)-t, mivel LKO(78,36)=LKO(36,6).
A=36, B=6
  • A ≠0
  • B ≠0
  • A maradékos osztás alapján 36/6 = 6, a maradék 0. Más alakban felírva:
  • 36 = 6 · 6 + 0
  • Keresd meg LKO(6,0)-t, mivel LKO(36,6)=LKO(6,0).
A=6, B=0
  • A ≠0
  • B =0, LKO(6,0)=6
Megmutattuk, hogy:
LKO(270,192) = LKO(192,78) = LKO(78,36) = LKO(36,6) = LKO(6,0) = 6
LKO(270,192) = 6

Az euklideszi algoritmus bizonyítása

Ha megvizsgáljuk az euklideszi algoritmust, akkor látjuk, hogy az alábbi tulajdonságokat használja fel:
  • LKO(A,0) = A
  • LKO(0,B) = B
  • Ha A = B⋅Q + R and B≠0, akkor LKO(A,B) = LKO(B,R), ahol Q egész, R 0 és B-1 közötti egész szám.
Az első két tulajdonság alapján meg tudjuk állapítani a LKO-t, ha valamelyik szám 0. A harmadik tulajdonság lehetővé teszi, hogy egy nagyobb, bonyolultabb feladatot leegyszerűsítsünk egy egyszerűbb, könnyebben megoldható feladatra.
Az euklideszi algoritmus ezen tulajdonságok felhasználásával a harmadik tulajdonság alapján egyre könnyebben megoldható feladatokra redukálja a problémát mindaddig, amíg a feladat az első két tulajdonság valamelyikével könnyen megoldhatóvá válik.
A magyarázat alapján meg tudjuk érteni, miért működik az eljárás.
Így tudjuk bebizonyítani, hogy LKO(A,0)=A:
  • Az A legnagyobb egész osztója A.
  • 0-nak minden szám osztója, mivel minden C egész számra felírható: C ⋅ 0 = 0. Ebből következik, hogy A 0-nak is osztója.
  • A legnagyobb szám, ami mind A-nak, mind 0-nak osztója, A.
Az LKO(0,B)=B bizonyítása hasonló a fentihez. (Ugyanaz a bizonyítás, csak A-t helyettesítjük B-vel).
Az LKO(A,B)=LKO(B,R) bizonyításához először be kell látni, hogy LKO(A,B)=LKO(B,A-B).
Tegyük fel, hogy van három egész szám, A, B és C, ahol A-B=C.
Bizonyítsuk be, hogy LKO(A,B) osztója C-nek:
A definíció alapján LKO(A,B) osztója A-nak. Ebből következik, hogy A többszöröse LKO(A,B)-nek, azaz X⋅LKO(A,B)=A, ahol X egész szám.
A definíció alapján LKO(A,B) osztója B-nek. Ebből következik, hogy B többszöröse LKO(A,B)-nek, azaz Y⋅LKO(A,B)=B, ahol Y egész szám.
A-B=C-t felírhatjuk az alábbi formában:
  • X⋅LKO(A,B) - Y⋅LKO(A,B) = C
  • (X - Y)⋅LKO(A,B) = C
A fentiekből látható, hogy LKO(A,B) osztója C-nek.
A fenti bizonyítást illusztrálja az alábbi ábra bal oldala:
Bizonyítsuk be, hogy LKO(B,C) osztója A-nak:
A definíció alapján LKO(B,C) osztója B-nek. Ebből következik, hogy B többszöröse LKO(B,C)-nek, azaz M⋅LKO(B,C)=B, ahol M egész szám.
A definíció alapján LKO(B,C) osztója C-nek. Ebből következik, hogy C többszöröse LKO(B,C)-nek, azaz N⋅LKO(B,C)=C, ahol N egész szám.
A-B=C-t felírhatjuk az alábbi formában:
  • B+C=A
  • M⋅LKO(B,C) + N⋅LKO(B,C) = A
  • (M + N)⋅LKO(B,C) = A
A fentiekből látható, hogy LKO(B,C) osztója A-nak.
A fenti bizonyítást illusztrálja az alábbi ábra
Bizonyítsuk be, hogy LKO(A,B)=LKO(A,A-B):
  • A definíció alapján LKO(A,B) osztója B-nek.
  • Bebizonyítottuk, hogy LKO(A,B) osztója C-nek.
  • Mivel LKO(A,B) osztója mind B-nek, mind C-nek, ezért B-nek és C-nek közös osztója.
LKO(A,B) kisebb, vagy egyenlő LKO(B,C)-nél, mert LKO(B,C) a „legnagyobb” közös osztója B-nek és C-nek.
  • A definíció alapján LKO(B,C) osztója B-nek.
  • Bebizonyítottuk, hogy LKO(B,C) osztója A-nak.
  • Mivel LKO(B,C) osztója mind A-nak, mind B-nek, ezért A-nak és B-nek közös osztója.
LKO(B,C) kisebb vagy egyenlő mint LKO(B,C), mert LKO(A,B) a „legnagyobb” közös osztója A-nak és B-nek.
Mivel LKO(A,B)≤LKO(B,C) és LKO(B,C)≤LKO(A,B), ebből következik, hogy:
LKO(A,B)=LKO(B,C)
Ami ekvivalens azzal, hogy
LKO(A,B)=LKO(B,A-B)
A fenti bizonyítást illusztrálja a lenti ábra jobb oldala.
Annak bizonyítása, hogy LKO(A,B)=LKO(B,R)
Bebizonyítottuk, hogy LKO(A,B)=LKO(B,A-B).
A kifejezések sorrendje nem számít, tehát mondhatjuk azt is, hogy LKO(A,B)=LKO(A-B,B).
Többszörösen alkalmazva az LKO(A,B)=LKO(A-B,B) szabályt ezt kapjuk:
LKO(A,B)=LKO(A-B,B)=LKO(A-2B,B)=LKO(A-3B,B)=...=LKO(A-Q⋅B,B)
De A= B⋅Q + R, ezért  A-Q⋅B=R
Ebből következik, hogy LKO(A,B)=LKO(R,B).
A kifejezések sorrendje nem számít, ezért
LKO(A,B)=LKO(B,R).

Szeretnél részt venni a beszélgetésben?

Még nincs hozzászólás.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.