Bestäm samtliga $x\in\mathbb{Z}$ som uppfyller $10x\equiv2\pmod{2023}$, samt ange hur många av dessa som ligger i intervallet $[3237,5260]$.
Diskret matematik · 2023-11-22
Uppgift 1
Visa lösningDölj lösning
Enligt definition gäller kongruensen om och endast om det finns något $y\in\mathbb Z$ sådant att
$$
10x=2+2023y.
$$
Detta är ekvivalent med den diofantiska ekvationen
$$
10x-2023y=2. \tag{*}
$$
Euklides algoritm ger
$$
2023=202\cdot10+3,\qquad 10=3\cdot3+1.
$$
Därmed är $\operatorname{SGD}(2023,10)=1$ och
$$
1=10-3\cdot3=10-3(2023-202\cdot10)=607\cdot10-3\cdot2023.
$$
Alltså är $(x,y)=(2\cdot607,2\cdot3)=(1214,6)$ en lösning till (*). Samtliga $x$-värden är
$$
x=1214+2023k,\qquad k\in\mathbb Z.
$$
Ett sådant $x$ ligger i det givna intervallet om och endast om
$$
3237\le1214+2023k\le5260
\Longleftrightarrow 1\le k\le2.
$$
Det finns alltså två sådana lösningar. Svar: $x=1214+2023k$ för $k\in\mathbb Z$, och precis två av dessa tal ligger i intervallet.