hitta alla lösningar

Hej

jag har fastnat lite på en uppgift som jag skulle behöva hjälp med:

Hitta alla lösningar till $12 x \equiv 28 (m o d 236)$

Jag kan konstatera att vi får gcd(12,28)=4 så vi kan väl skriva om uppgiften till $3 x \equiv 7 (m o d 236)$

Hur ska man sedan ta sig vidare härifrån? ska man tex sätta $3 x \equiv 7 (m o d 243)$ och sedan dela med 3 så vi får $x \equiv 7 (m o d 81)$

B.N. skrev :
Hej
jag har fastnat lite på en uppgift som jag skulle behöva hjälp med:
Hitta alla lösningar till $12 x \equiv 28 (m o d 236)$
Jag kan konstatera att vi får gcd(12,28)=4 så vi kan väl skriva om uppgiften till $3 x \equiv 7 (m o d 236)$

Det är okej att addera, subtrahera och multiplicera kongruenser. Men när man ska "dela" med något måste alla varningsblinkers slås på och basunerna ljuda. Jag skulle börja med att konstatera att gcd(236,12)=4 vilket delar 28, alltså har kongruensrelationen lösningar. Det är "tillåtet" att dela med 4.

$3x\equiv 7 \,\pmod{59}$

Nu ser vi förhoppningsvis att 20 är inversen till 3 (ty 20*3=60=59+1), vi multiplicerar båda led med $3^{-1}$ dvs 20.

$x\equiv 20\cdot 7 \,\pmod{59}$

$x\equiv 22 \,\pmod{59}$

alla lösningar ges av $x=22+59n,\quad n\in \mathbb{Z}$

Ett alternativ är att du redan från början löser den diofantiska ekvationen $12x-236y=28$

Svara