Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

2. fejezet - Számelméleti algoritmusok

2. fejezet - Számelméleti algoritmusok

2.1. Alapfogalmak

2.1. Definíció. Az oszthatóság

Azt mondjuk, hogy a egész szám osztja az egész számot, ha az osztásnak zérus a maradéka, azaz, ha létezik olyan egész szám, hogy . Jelölésben: . A számot az osztójának nevezzük. Az szám a többszöröse.

2.2. Definíció. Prímszám

Prímszámnak nevezzük azt az 1-nél nagyobb egész számot, amelynek csak az 1 és saját maga a pozitív osztója.

2.3. Tétel. A maradékos osztás tétele

Ha egész szám, pedig pozitív egész szám, akkor egyértelműen létezik olyan és egész szám, hogy

A szám neve hányados, neve maradék. A hányados és a maradék felírható:

2.4. Definíció. Közös osztó

Azt mondjuk, hogy a egész szám az és egészek közös osztója, ha mindkét számot osztja (azaz és ).

2.5. Definíció. Lineáris kombináció

Az egész számot az és egészek (egész) lineáris kombinációjának nevezzük, ha létezik olyan és egész szám, hogy . Az és számokat a lineáris kombináció együtthatóinak nevezzük. Az és számok összes lineáris kombinációjának halmazát -vel jelöljük.

Speciálisan lineáris kombinációk az és az számok is. Adott egész előállításakor az és együtthatók nem egyértelműek, azaz ha léteznek, akkor több számpár is megfelelhet erre a célra, amint az az alábbi példából is látható.

2.1. Példa. Legyen két szám . Határozzuk meg az értékeket az , együtthatókra!

2.6. Tétel. A közös osztó tulajdonságai

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

[1.] vagy .

[2.] Ha és , akkor .

[3.] A közös osztó osztója az és szám minden lineáris kombinációjának is, azaz -re .