Diskret matematik · 2025-10-22

Uppgift 2

Uppgift 2

Betrakta den Diofantiska ekvationen $35x + 21y = 2100$.

(a)

Bestäm den allmänna lösningen till ekvationen.

(b)

Bestäm antalet lösningar $(x,y)$ där $x,y\geq 0$.

(c)

Bestäm summan av alla heltal $x$ som ingår i en lösning $(x,y)$ där $x,y\geq 0$.

Visa lösningDölj lösning

Vi delar först båda led med $\SGD(35,21)=7$ och får ekvationen $7x+5y=300$. Nu har vi att $\SGD(5,3)=1$, så ekvationen har lösningar.

Vi löser först $5x+3y=1$. Man kan direkt se att $x=-1$, $y=2$ ger en lösning, så $x=-300$, $y=2\cdot 300=600$ är en lösning till ursprungliga ekvationen. Allmän lösning är då \[ \begin{cases} x = & 3k-300 \\ y = & 600-5k, \end{cases}\qquad k\in\mathbb Z. \]
Positivitetsvillkor: $x\geq 0$ och $y \geq 0$ ger $100 \leq k \leq 120$, så vi har $21$ lösningar där $x,y \geq 0$.
Den lösning med minsta $x$ är $(0,100)$ och den med störst $x$ är $(60,0)$ Formeln för aritmetisk summa ger då att summan av alla de $21$ värden som ingår är $\frac{0+60}{2}\cdot 21 = 630$.