Uppgift 1
(a)
Bestäm alla lösningar till diofantiska ekvationen $25x+16y=1$.
(b)
Ange alla lösningar till den diofantiska ekvationen $25x+16y=1000$ sådana att $x,y>0$. (Tips: Det kan vara praktiskt att utgå från en ”enkel” partikulärlösning.)
Hela algebra · 2018-06-11
Uppgift 1
Visa lösningDölj lösning
(a) Vi börjar med Euklides algoritm:
$$
\begin{aligned}
25&=1\cdot16+9,\\
16&=1\cdot9+7,\\
9&=1\cdot7+2,\\
7&=3\cdot2+1.
\end{aligned}
$$
så $\operatorname{SGD}(25,16)=1$ och vi kan lösa ekvationen genom att köra Euklides algoritm baklänges:
$$
1=7-3\cdot2=7-3\cdot(9-1\cdot7)=4\cdot7-3\cdot9
=4\cdot(16-1\cdot9)-3\cdot9
=4\cdot16-7\cdot9
=4\cdot16-7\cdot(25-1\cdot16)=11\cdot16-7\cdot25.
$$
Vi får att $(x,y)=(-7,11)$ är en partikulärlösning, så den allmänna lösningen ges därmed av
$$
\begin{cases}
x=-7+16k,\\
y=11-25k
\end{cases}
\qquad k\in\mathbb Z.
$$
(b) Multipliceras lösningen i (a) med $1000$ fås partikulärlösning $(x,y)=(-7000,11000)$. Det går bra att arbeta med den, men tipset får oss kanske att se den enklare lösningen $(x,y)=(40,0)$. Därmed är den allmänna lösningen
$$
\begin{cases}
x=40+16k,\\
y=-25k
\end{cases}
\qquad k\in\mathbb Z.
$$
Villkoren $x,y>0$ ger $-2.5=-\frac{40}{16}<k<0$, så $k=-2$ eller $k=-1$, vilket ger $(x,y)=(8,50)$ respektive $(x,y)=(24,25)$.