Uppgift 2

Sambandet $45x\equiv8\pmod{13}$ kan skrivas $45x=8+13y$ för något heltal $y$, alltså $45x-13y=8$. Med hjälp av Euklides algoritm finner vi en lösning till $45x-13y=1$, nämligen $x_0=-2$, $y_0=-7$. Därmed är

$$x_1=-2\cdot8=-16,\qquad y_1=-7\cdot8=-56$$

en lösning till $45x-13y=8$. Den allmänna lösningen är

$$x=-16+13k,\qquad y=-56+45k.$$

Vi vill ha $100<x<200$, så

$$100<-16+13k<200,$$

vilket medför

$$\frac{116}{13}<k<\frac{216}{13}.$$

Eftersom $\frac{116}{13}=8+\frac{12}{13}$ och $\frac{216}{13}=16+\frac{8}{13}$, är $9\le k\le16$.

Svar: $x=-16+13k$, där $9\le k\le16$.