Uppgift 1
Betrakta den diofantiska ekvationen
$$100x + 123y = 5.$$
(a)
Bestäm alla lösningar.
(b)
Ange den lösning som har minsta möjliga positiva $y$.
Hela algebra · 2018-12-05
Uppgift 1
Visa lösningDölj lösning
(a) Vi börjar med Euklides algoritm:
$$
\begin{aligned}
123&=1\cdot100+23,\\
100&=4\cdot23+8,\\
23&=2\cdot8+7,\\
8&=1\cdot7+1.
\end{aligned}
$$
så $\operatorname{SGD}(123,100)=1$ och vi kan lösa hjälpekvationen $100x+123y=1$ genom att köra Euklides algoritm baklänges:
$$1=8-1\cdot7=8-1\cdot(23-2\cdot8)=3\cdot8-1\cdot23
=3\cdot(100-4\cdot23)-1\cdot23=3\cdot100-13\cdot23
=3\cdot100-13\cdot(123-1\cdot100)=16\cdot100-13\cdot123.$$
Vi får att $(x,y)=(16,-13)$ är en partikulärlösning till hjälpekvationen. Multipliceras denna med $5$ fås en partikulärlösning till vår ekvation, så den allmänna lösningen ges därmed av
$$
\begin{cases}
x=80+123k,\\
y=-65-100k
\end{cases}
\qquad k\in\mathbb Z.
$$
(b) Vi får minsta möjliga positiva $y$ för $k=-1$, vilket ger $(x,y)=(-43,35)$.