Uppgift 1

(a) Vi börjar med Euklides algoritm:

$$ \begin{aligned} 51&=1\cdot31+20,\\ 31&=1\cdot20+11,\\ 20&=1\cdot11+9,\\ 11&=1\cdot9+2,\\ 9&=4\cdot2+1. \end{aligned} $$

så $\operatorname{SGD}(51,31)=1$ och vi kan lösa hjälpekvationen
$$31x+51y=1. \tag{1}$$
genom att köra Euklides algoritm baklänges:
$$ \begin{aligned} 1&=9-4\cdot2=9-4\cdot(11-1\cdot9)=5\cdot9-4\cdot11\\ &=5\cdot(20-1\cdot11)-4\cdot11=5\cdot20-9\cdot11\\ &=5\cdot20-9\cdot(31-1\cdot20)=14\cdot20-9\cdot31\\ &=14\cdot(51-1\cdot31)-5\cdot20=31\cdot(-23)+51\cdot14. \end{aligned} $$
Vi får att $(x,y)=(-23,14)$ löser hjälpekvationen (1). Multipliceras denna lösning med $3$ fås en partikulärlösning $(x,y)=(-69,42)$ till vår ekvation, så den allmänna lösningen ges därmed av
$$ \begin{cases} x=-69+51k,\\ y=42-31k \end{cases} \qquad k\in\mathbb Z. $$

(b) Villkoret $|y|<31$ ger $-31<42-31k<31$ som har lösningarna $k=1,2$, vilket insatt i lösningsformeln ger $(x,y)=(-18,11)$ samt $(x,y)=(33,-20)$.