Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

2.5. A lineáris kongruencia egyenlet

2.5. A lineáris kongruencia egyenlet

2.15. Definíció. Kongruencia

Az és egész számokat kongruensnek mondjuk az modulus szerint, ha az szerinti osztás utáni maradékaik megegyeznek, vagy ami ugyanaz: ha . Jelölésben: .

2.16. Tétel. A kongruenciákon végezhető műveletek tétele

Legyen és Akkor igazak az alábbi állítások:

2.17. Definíció. A lineáris kongruencia egyenlet

Az

egyenletet, melyben az ismeretlen, lineáris kongruencia egyenletnek nevezzük.

2.18. Tétel. A lineáris kongruencia egyenlet megoldhatósági tétele

Legyen az 2.2 egyenletre Az 2.2 lineáris kongruencia egyenletnek akkor és csak akkor van megoldása, ha Ha van megoldás, akkor végtelen sok van, de ezeket egy számú megoldást tartalmazó úgynevezett megoldás alaprendszerből megkaphatjuk az egész számú többszöröseinek a hozzáadásával. Az alaprendszer elemeit a intervallumból választjuk ki. Az alaprendszer megoldásai az alábbi módon írhatók fel:

Bizonyítás. Legyen , , . Akkor a lineáris kongruencia egyenlet alakra írható át, amiből az egyenlet adódik, vagyis hogy a az és az lineáris kombinációja. Ha azt akarjuk, hogy legyen megoldás, akkor fenn kell álljon, ahol az és lineáris kombinációinak a halmaza. Ha ez nem áll fenn, akkor nincs megoldás. A lineáris kombinációban lévő elemeket viszont a legnagyobb közös osztó osztja, és csak azokat osztja a lineáris kombinációk halmazának jellemzési tétele szerint. Legyen most olyan, hogy . Akkor van olyan egész szám, hogy . A legnagyobb közös osztó viszont az és az lineáris kombinációja, azaz van olyan és egész, hogy . Ez a formula viszont egyenértékű az lineáris kongruencia egyenlettel, ha az szerinti maradékokat nézzük. Beszorozva itt -val adódik, amiből azonnal látható, hogy az megoldás. További megoldásokat kapunk, hogyha képezzük az , számokat, ugyanis a lineáris kongruencia egyenletbe történő behelyettesítés után az , jelenik meg a baloldalon, ahol a második tag osztható -nel, mert a az -t osztja, így az megmarad, tehát ez a tag nem módosítja az első tag általi maradékot. Ezeket a megoldásokat alapmegoldásoknak nevezzük. Nyílvánvaló, hogy ha egész többszörösét hozzáadom az alapmegoldásokhoz, akkor újra megoldást kapok, csak az már nem lesz alapmegoldás (nem viselkedik maradékként).

A lineáris kongruencia egyenlet megoldására algoritmus konstruálható, ugyanis a kívánt a kibővített euklideszi algoritmusból megkapható.

2.5. Példa. Oldjuk meg a egyenletet!

Láttuk, hogy . A 136 osztható 68-cal, így az egyenletnek van megoldása. Az alaprendszer 68 különböző elemet tartalmaz. Most

A megoldások:

2.19. Definíció. A multiplikatív inverz

Legyen a lineáris kongruencia egyenlet

alakú (azaz és legyenek relatív prímek). Az egyenlet egyetlen alapmegoldását az szám szerinti multiplikatív inverzének nevezzük. Jelölése:

A multiplikatív inverz meghatározása történhet a lineáris kongruencia megoldó 2.5.1. algoritmus segítségével. Természetesen a FOR ciklus alkalmazására az eljárásban nem lesz szükség.

2.6. Példa. Oldjuk meg: .

Az megoldását keressük.

Láthatóan , tehát van multiplikatív inverz.

Az együtthatója , aminek a 8 szerinti maradéka . Tehát az 5 multiplikatív inverze 8-ra nézve éppen saját maga.

Ellenőrzés: