Diskret matematik · 2026-03-12
Bestäm $\operatorname{SGD}(132, 180)$ med Euklides algoritm.
Hitta alla icke-negativa heltalslösningar till $11x + 15y = 135$.
Bestäm det minsta positiva heltal $b$ för vilket ekvationen $132x + 180y = b$ har heltalslösningar, samt finn en lösning.
(a) Euklides algoritm ger $180=1\cdot132+48$, $132=2\cdot48+36$, $48=1\cdot36+12$ och $36=3\cdot12+0$. Den sista icke-försvinnande resten är $12$. Svar: $\operatorname{SGD}(132,180)=12$.
(b) Vi skriver $11x=135-15y=15(9-y)$. Eftersom $\operatorname{SGD}(11,15)=1$ måste $15$ dela $x$. Sätt $x=15k$. Då blir $y=9-11k$. Villkoren $x\ge0$ och $y\ge0$ ger $0\le k<1$, så $k=0$. Svar: $(x,y)=(0,9)$.
(c) Ekvationen $Ax+By=C$ har heltalslösningar om och endast om $\operatorname{SGD}(A,B)$ delar $C$. Det minsta positiva $b$ är därför $12$. Baklänges från Euklides algoritm får vi $12=3\cdot180-4\cdot132$. Svar: $b=12$, till exempel $x=-4$, $y=3$.