Diskret matematik · 2026-04-22
Diofantiska ekvationer. Betrakta den diofantiska ekvationen $154x+198y=n$.
Beräkna $\operatorname{SGD}(154,198)$.
För $n=2026$, bestäm om ekvationen är lösbar. Motivera ditt svar.
Bestäm det minsta positiva heltalet $n$ för vilket ekvationen har heltalslösningar samt hitta alla lösningar till den.
Vi studerar ekvationen
$$
154x+198y=n.
$$
(a) Primtalsfaktorisering:
$$
154=2\cdot7\cdot11,\qquad 198=2\cdot3^2\cdot11.
$$
Alltså är $\gcd(154,198)=2\cdot11=22$.
(b) Ekvationen är lösbar om och endast om $22\mid n$. Eftersom
$$
2026=22\cdot92+2
$$
är $2026$ inte delbart med $22$. Ekvationen är därför inte lösbar.
(c) Minsta positiva $n$ är $\gcd(154,198)=22$. Dividera ekvationen med $22$:
$$
7x+9y=1.
$$
Med utvidgade Euklides algoritm får vi
$$
9=7\cdot1+2,\qquad 7=2\cdot3+1,
$$
och därmed
$$
1=7-2\cdot3=7-(9-7)\cdot3=4\cdot7-3\cdot9.
$$
Alltså kan vi välja $x_0=4$ och $y_0=-3$. Alla lösningar är
$$
x=4+9t,\qquad y=-3-7t,\qquad t\in\mathbb Z.
$$