20.13. Tétel
Lineáris kongruenciák és lineáris diofantoszi egyenletek megoldhatósága
Legyen a és b tetszőleges, 0\lt m pedig valamilyen pozitív egész szám. Ekkor az ax\equiv b\pmod m lineáris kongruencia akkor és csak akkor oldható meg, ha megoldható az alábbi úgynevezett lineáris diofantoszi egyenlet:
Itt megoldás egy olyan egész számpárt értünk, amelyeket az egyenletbe x és y helyére behelyettesítve teljesül az egyenlőség.
Egy tetszőleges s egész szám által reprezentált [s]_m maradékosztály akkor és csak akkor megoldása az ax\equiv b\pmod m lineáris kongruenciának, ha létezik olyan t egész szám, hogy az (s;t) számpár megoldása a fenti egyenletnek, azaz fennáll az
egyenlőség.
Jelöljük (a,m)-mel az a és m egész számok kitüntetett közös osztóját. A fenti lineáris diofantoszi egyenletnek – és így a neki megfelelő ax\equiv b\pmod m lineáris kongruenciának – akkor és csak akkor létezik megoldása, ha teljesül az (a,m)|b oszthatóság.
♣