Hela algebra · 2022-08-10
Betrakta den diofantisk ekvation
$$15x+13y=11.$$
Bestäm alla lösningar till ekvationen.
Ange den eller de lösningar som minimerar $\lvert x-y\rvert$.
För vilka primtal $p$ finns det lösningar till den diofantiska ekvationen $15x+py=11$?
(a) Vi börjar med Euklides algoritm:
$$
15=1\cdot13+2,\qquad13=6\cdot2+1,\qquad2=2\cdot1.
$$
Så $\operatorname{SGD}(15,13)=1$ och vi kan lösa hjälpekvationen $15x+13y=1$ genom att köra Euklides algoritm baklänges:
$$1=13-6\cdot2=13-6\cdot(15-1\cdot13)=15\cdot(-6)+13\cdot7.$$
Vi får att $(x,y)=(-6,7)$ är en partikulärlösning till hjälpekvationen. Multipliceras denna med $11$ fås en partikulärlösning till vår ekvation, så den allmänna lösningen ges därmed av
$$
\begin{cases}
x=-66+13k,\\
y=77-15k
\end{cases}
\qquad k\in\mathbb Z.
$$
(b) Insättning av lösningen ger $x-y=-143+28k$. Vi behöver alltså hitta den rest av $143$ modulo $28$ som ligger närmast $0$ på tallinjen, vilket är $3$ och som fås för $k=5$. Vi finner alltså det minsta värdet $\lvert x-y\rvert=3$ för $(x,y)=(-1,2)$.
(c) Ekvationen har lösningar om och endast om $\operatorname{SGD}(15,p)\mid11$. Eftersom $15=3\cdot5$ är
$$
\operatorname{SGD}(15,p)=
\begin{cases}
3&\text{om }p=3,\\
5&\text{om }p=5,\\
1&\text{annars}.
\end{cases}
$$
Så ekvationen är lösbar för alla primtal $p$ utom $3$ och $5$.