Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 2. témakör
5. lecke: Moduláris aritmetika- Mi a moduláris aritmetika?
- Modulo művelet
- Játék a modulóval
- Maradékosztály
- Kongruencia reláció
- Ekvivalence reláció
- Maradékos osztásra vonatkozó tétel
- Moduláris összeadás és kivonás
- Moduláris összeadás
- Moduláris kihívás (összeadás és kivonás)
- Moduláris szorzás
- Moduláris szorzás
- Moduláris hatványozás
- Gyors moduláris hatványozás
- Gyors moduláris hatványozás
- Moduláris inverz
- Az euklideszi algoritmus
© 2023 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés
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.