2.40 Den Diofantiska ekvationen

ax + by = c

har en lösning om och endast om SGD(a, b) | c. Alltså har både (b) och (c) lösningar, men inte (a), eftersom SGD(6, 15) = 3.

2.45 Vi letar efter den lösning till Diofantiska ekvationen

35x + 45y = 10000, x ≥ 0, y ≥ 0,  (1)

där x är så stor som möjligt. Först, simplificera ekvationen genom att dela med 5 så att man får

7x + 9y = 2000.  (2)

Vi noterar att SGD(7, 9) = 1 och att

1 = 7 · 4 + 9 · (−3).  (3)

(Om du inte ser dessa fakta direkt, då kan du använda Euklides’ algoritm). Om vi multiplicerar (3) med 2000, då får vi EN lösning till (2), nämligen x = 8000, y = −6000. Då ges den allmäna lösningen till (2) av

x = 8000 − 9n, y = −6000 + 7n.  (4)

Vi behöver x ≥ 0, y ≥ 0 och x maximal. Därför behöver vi y ≥ 0 och minimal. Då ser man att man borde ta n = ⌈\frac{6000}{7}⌉ = 858, som ger lösningen y = 6 och x = 278.

Svar : 278.