Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

2.2. A legnagyobb közös osztó

2.2. A legnagyobb közös osztó

2.7. Definíció. Legnagyobb közös osztó

Az alább megadott egész számot az és egész számok legnagyobb közös osztójának nevezzük. Jele: .

2.8. Definíció. Relatív prímek

Az és egész számokat relatív prímeknek nevezzük, ha .

2.9. Tétel. A legnagyobb közös osztó elemi tulajdonságai

Legyen a egész az és egészek legnagyobb közös osztója. Akkor fennállnak az alábbi állítások:

[1.] kivéve ha és .

[2.] .

[3.] .

[4.] .

[5.] Ha közös osztó és , akkor .

[6.] A legnagyobb közös osztó minden lineáris kombinációnak osztója, azaz -re .

2.10. Tétel. A legnagyobb közös osztó reprezentációs tétele

Ha az és egész számok nem mindegyike zérus, akkor a legnagyobb közös osztó megegyezik a két szám pozitív lineáris kombinációinak minimumával.

Bizonyítás. A bizonyítás menete az lesz, hogy megmutatjuk, hogy és , amiből következik az állítás.

Az megmutatása úgy történik, hogy belátjuk, hogy közös osztó, ami nem lehet nagyobb, mint a legnagyobb közös osztó. Azt, hogy közös osztó azáltal látjuk be, hogy az osztási maradéka zérus. Csak az számra végezzük el, -re ugyanígy megy a bizonyítás. Osszuk el tehát -t -gal és számítsuk ki a maradékot! Legyen a hányados. Az maradékra igaz, hogy . Akkor

Az egyenlőtlenség közepén álló maradék az és a lineáris kombinációja. A baloldali egyenlőtlenség miatt nem lehet negatív, a jobboldali egyenlőtlenség miatt pedig kisebb, mint a pozitív lineáris kombinációk közül a legkisebb. Emiatt csak zérus lehet. Tehát az osztja az számot.

A abból következik, hogy a legnagyobb közös osztó osztja az összes lineáris kombinációt, így -ot is. Ekkor azonban nem lehet nagyobb, mint , hiszen annak osztója.

A tétel következményei:

[1.] A közös osztó osztja a legnagyobb közös osztót, ugyanis a legnagyobb közös osztó az és egészek lineáris kombinációja a tétel szerint, amit a közös osztó oszt.

[2.] Tetszőleges nemnegatív egészre

Ugyanis -ra az állítás triviális, -ra pedig

(Lássuk be, hogy az utolsó egyenlőségjel valóban igaz, azaz a lineáris kombinációkban mindkét számpár esetén ugyanaz az , megfelelő választás!)

2.11. Tétel. A lineáris kombinációk halmazának jellemzése

Legyen a egész többszöröseinek a halmaza. Állítás:

Bővebben: az minden eleme egész többszöröse és ha egy szám egész többszöröse, akkor az az szám az és lineáris kombinációja is.

Bizonyítás. Megmutatjuk, hogy és , amiből következik az állítás. Az eset: és , amiből következik, hogy van olyan , hogy . Ha , akkor

mert .

Az eset: .

Ha , akkor van olyan , hogy

2.12. Tétel. A legnagyobb közös osztó redukciós tétele

Tetszőleges és két egész szám esetén fennáll, hogy

Bizonyítás. Legyen és Azt fogjuk bizonyítani, hogy és , amiből következik a tétel állítása.

Megmutatjuk, hogy és is fennáll, amiből a kölcsönös oszthatóság már következik.

megmutatása:

megmutatása: