Diskret matematik · 2023-11-22

Uppgift 1

Hela tentan
Uppgift 1

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]$.

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.

Figur