System med kongurenser

Här är bilden av din uppgift, så att folk slipper klistra in en inte-ens-klickbar länk för att hitta den:

Här är en förklaring till hur du borde ha gjort det själv.

Hur långt har du kommit själv på uppgiften? Det står i Pluggakutens regler att du skall visa hur du har försökt och hur långt du har kommit. /moderator

Tack! Jag förstår inte riktigt hur jag ska börja

Jag har inte kommit på någon komplett lösning, men detta kan kanske vara en början:

$x\equiv a (mod 13) \Rightarrow ax\equiv a^2 (mod 13)$

Om vi då börjar med de a och x som ligger mellan 0 och 12, så kan man konstatera att för dem gäller a=x. Sedan kan man lista deras kvadrater (0, 1, 4, 9, ... 144) och genom prövning inse att det är bara 1, 49 och 121 som är kongruenta med 1 (mod 12). Då har vi att a = x = 1, a = x = 7 och a = x = 11 är lösningar. Men jag har inte riktigt lyckats utvidga detta till a>12.

Någon annan?

5 också. 

Stämmer med 5!

Men hur går man vidare?

Vi har att $x \equiv a (\mod 12)$ och $x \equiv a (\mod 13)$. Man borde komma vidare därifrån, men jag har inte försökt formulera nånting.

Om $a$ inte har någon multiplikativ invers i  $\mathbb{Z}_{12}$ så saknar systemet lösning p.g.a. den första kongruensen. Om $a$ har en multiplikativ invers i $\mathbb{Z}_{12}$ så kan vi skriva om systemet av kongruenserna enligt

$x \equiv a \text{ (mod 12)}$

$x \equiv a \text{ (mod 13)}$

Och den kinesiska restsatsen säger oss att vi kan hitta en lösning eftersom att 12 och 13 är relativt prima. Systemet har alltså en lösning om och endast om $a$ har en multiplikativ invers i $\mathbb{Z}_{12}$.