Uppgift 1
(a)
Bestäm alla lösningar till den diofantisk ekvation $7x+15y=1$.
(b)
Lös kongruensen $7x\equiv1\pmod{15}$.
(c)
Bestäm för vilka primtal $p$ som kongruensen $px\equiv 1\pmod{15}$ har lösning.
Hela algebra · 2018-05-07
Uppgift 1
Visa lösningDölj lösning
(a) Man ser enkelt en partikulärlösning $(x,y)=(-2,1)$, så eftersom $\operatorname{SGD}(15,7)=1$ ges den allmänna lösningen av
$$
\begin{cases}
x=-2+15k,\\
y=1-7k
\end{cases}
\qquad k\in\mathbb Z.
$$
(b) Kongruensen är ekvivalent med att $7x-1=15l$, för $l\in\mathbb Z$, vilket är precis den diofantiska ekvationen i (a), med $y=-l$. De möjliga värdena på $x$ är därmed $x=-2+15k$, för $k\in\mathbb Z$, vilket kan skrivas som $x\equiv -2\equiv13\pmod {15}$.
(c) Att lösa kongruensen $px\equiv1\pmod {15}$ är ekvivalent med att lösa den diofantiska ekvationen $px+15y=1$, som är lösbar om och endast om $\operatorname{SGD}(p,15)$ delar $1$, dvs. för alla primtal $p$ utom $3$ och $5$.