Uppgift 1

(a) Lösningar $x$ till kongruensen $5x\equiv3\pmod{163}$ motsvarar lösningar till den diofantiska ekvationen $5x+163y=3$. Vi börjar därför med Euklides algoritm:
$$ 163=32\cdot5+3,\qquad 5=1\cdot3+2,\qquad 3=1\cdot2+1. $$
Så $\operatorname{SGD}(163,5)=1$ och vi kan lösa hjälpekvationen $5x+163y=1$ genom att köra Euklides algoritm baklänges:
$$ 1=3-1\cdot2=3-1\cdot(5-1\cdot3)=2\cdot3-1\cdot5 =2\cdot(163-32\cdot5)-1\cdot5=2\cdot163-65\cdot5. $$
Vi får att $(x,y)=(-65,2)$ löser hjälpekvationen. Multipliceras denna lösning med $3$ fås en partikulärlösning $(x,y)=(-195,6)$ till vår ekvation, så den allmänna lösningen ges därmed av
$$ \begin{cases} x=-195+163k,\\ y=6-5k \end{cases} \qquad k\in\mathbb Z. $$
Den sökta lösningen $x$ uppfyller $0<x\le163$, vilket ger $k=2$. Insatt i lösningsformeln ger detta $x=131$.

(b) Eftersom $23$ är ett primtal ger Fermats lilla sats att $2^{22}\equiv1\pmod{23}$, så
$$ 2^{2975}+2^{224}\equiv(-1)^{75}+2^{22\cdot10+4} \equiv-1+(2^{22})^{10}2^4\equiv-1+1^{10}\cdot16=15\pmod{23}, $$
så resten är $15$.