Uppgift 2
För ett heltal $a$, betrakta den diofantiska ekvationen $
170x + 289 y = a.
$
(a)
Bestäm det minsta positiva heltal $a$ som gör att ekvationen har lösningar.
(b)
Bestäm två olika lösningar till ekvationen $170x + 289 y=17$.
Diskret matematik · 2024-04-17
Uppgift 2
Visa lösningDölj lösning
- Den diofantiska ekvationen har en lösning om och endast om $\SGD(170,289) \mid a$, enligt utlärd sats. Vi kan med Euklides algoritm beräkna $\SGD(170,289)$: \[\begin{aligned} 289 &= 170 + 119 \\ 170 &= 119 + 51 \\ 119 &=2\cdot 51 + 17 \\ 51 &= 3\cdot 17 + 0. \end{aligned}\] Så största gemensamma delaren är $17$. Alltså finns det en lösning omm $17 \mid a$, och det minsta positiva värdet på $a$ som uppfyller detta är $a=17$.
- Genom division med $17$ ser vi att ekvationen är ekvivalent med \[
10x + 17 y = 1.
\] Vi vet sedan tidigare att $17\cdot 3 = 51$, så $10(-5) + 17\cdot 3 = 1$. En lösning är då $(x,y) = (-5, 3)$. Alla andra lösningar skiljer sig från denna, enligt utlärd sats, med heltalsmultiplar av $(17,-10)$; dvs, den allmänna lösningen ges av \[ (x,y) = (-5, 3) + k(17, -10) \quad\text{där $k \in \mathbb{Z}$}. \] Alltså fås en till lösning av $(x,y) = (-5,3) + (17, -10) = (12, -7)$.
Svar: $(x,y) = (-5,3)$ eller $(12, -7)$ är två lösningar.