Lineære kongruenser

[andersfk]

Noen som kan gi hint til hvordan jeg løser denne typen problemer:

Vil finne alle heltall (x,y) som løser følgende ligningssett:

$a_{1}x+b_{1}y\equiv c_1(\text{mod }d)$
$a_{2}x+b_{2}y\equiv c_2(\text{mod }d)$

Alt bortsett fra x og y er konstanter.

Takk.

[Shantel]

Du må bruke The Chinese Remainder Theorem.

[daofeishi]

Nei, det gaar nok ikke. Det kinesiske restklasseteoremet kan bare brukes dersom moduloene er parvis relativt primiske, noe de ikke er i dette tilfellet.

[andersfk]

Lurer på om jeg ikke har funnet en metode nå.

Ganger opp en eller begge ligningene slik at konstantene foran $y$ er like (her kreves det da at faktoren det ganges med er relativt primisk med $d$).

Trekker de to kongruensene fra hverandre, slik at y-leddene forsvinner og det står igjen et uttrykk

$a_{3}x\equiv c_3(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{d})$

Denne kan da løses på "vanlig måte" med $x_0=\overline{a_3}\cdot c_3$ .

Samme fremgangsmåte for $y$.