youproof.orgDeep Math. Human Access.

20.13. Tétel

Lineáris kongruenciák és lineáris diofantoszi egyenletek megoldhatósága

Legyen aa és bb tetszőleges, 0<m0\lt m pedig valamilyen pozitív egész szám. Ekkor az ax≡b(modm)ax\equiv b\pmod m lineáris kongruencia akkor és csak akkor oldható meg, ha megoldható az alábbi úgynevezett lineáris diofantoszi egyenlet:

ax+my=bax+my=b

Itt megoldás egy olyan egész számpárt értünk, amelyeket az egyenletbe xx és yy helyére behelyettesítve teljesül az egyenlőség.

Egy tetszőleges ss egész szám által reprezentált [s]m[s]_m maradékosztály akkor és csak akkor megoldása az ax≡b(modm)ax\equiv b\pmod m lineáris kongruenciának, ha létezik olyan tt egész szám, hogy az (s;t)(s;t) számpár megoldása a fenti egyenletnek, azaz fennáll az

as+mt=bas+mt=b

egyenlőség.

Jelöljük (a,m)(a,m)-mel az aa és mm egész számok kitüntetett közös osztóját. A fenti lineáris diofantoszi egyenletnek – és így a neki megfelelő ax≡b(modm)ax\equiv b\pmod m lineáris kongruenciának – akkor és csak akkor létezik megoldása, ha teljesül az (a,m)∣b(a,m)|b oszthatóság.

♣