Uppgift 1
Betrakta den diofantiska ekvationen $23x + 31y = 1400$.
(a)
Bestäm alla lösningar.
(b)
Visa att alla lösningar $(x, y)$ uppfyller $8 \mid x + y$.
(c)
Bestäm alla lösningar med $x, y > 0$. Svaren skall anges uträknade.
Hela algebra · 2019-06-10
Uppgift 1
Visa lösningDölj lösning
(a) Vi börjar med Euklides algoritm:
$$31=1\cdot23+8,\qquad23=2\cdot8+7,\qquad8=1\cdot7+1.$$
Så $\operatorname{SGD}(23,31)=1$ och vi kan lösa hjälpekvationen $23x+31y=1$ genom att köra Euklides algoritm baklänges:
$$1=8-1\cdot7=8-(23-2\cdot8)=3\cdot8-23=3(31-23)-23=3\cdot31-4\cdot23.$$
Vi får att $(x,y)=(-4,3)$ är en partikulärlösning till hjälpekvationen. Multipliceras denna med $1400$ fås en partikulärlösning till vår ekvation, så den allmänna lösningen ges därmed av
$$x=-5600+31k,\qquad y=4200-23k,\qquad k\in\mathbb Z.$$
(b) Lösningarna $(x,y)$ uppfyller
$$x+y=-1400+8k\equiv0\pmod8.$$
(c) Villkoren $x,y>0$ ger
$$\frac{5600}{31}<k<\frac{4200}{23},$$
så
$$180+\frac{20}{31}<k<182+\frac{14}{23},$$
vilket ger att $k=181$ eller $k=182$. Svar: $(x,y)=(11,37)$ eller $(x,y)=(42,14)$.