Dionfantisk Ekvation

Du har upptäckt att $4\cdot0+2=2$, vilket är en bra utgångspunkt. Om vi nu multiplicerar båda led med $14$ får vi:

$4\cdot0+2\cdot14=28$

Nu har vi upptäckt ett talpar $(x,y)$ som uppfyller vår diofantiska ekvation, nämligen $x=0$ och $y=14$. Det finns dock fler lösningar. Vet du hur vi kan hitta dem?

Det är när jag ska hitta de resterande lösningarna som jag stöter på problem. 

Andersson_4 skrev:

Det är när jag ska hitta de resterande lösningarna som jag stöter på problem. 

Det är den enkla delen. Om vi har ax1 + by1 = c, så gäller att x2 = x1+b, y2 = y1-a är en ny lösning, eftersom a*b + b*(-a) = 0.

Laguna skrev:

Andersson_4 skrev:

Det är när jag ska hitta de resterande lösningarna som jag stöter på problem. 

Det är den enkla delen. Om vi har ax1 + by1 = c, så gäller att x2 = x1+b, y2 = y1-a är en ny lösning, eftersom a*b + b*(-a) = 0.

Fast om du använder $a\cdot b$ och $-a\cdot b$ kommer du att missa lösningar. I detta fall får du enligt din metod att nästa lösning ligger vid $x=0+2=2$ och $y=14-4=10$, men det finns faktiskt en lösning $x=1$, $y=12$ däremellan.

Det är därför viktigt att istället för att addera och subtrahera $a\cdot b$ så adderar vi och subtraherar vi $\text{mgm}(a,b)$ eftersom vi då inte missar några lösningar. Jag gillar att ställa upp det så här:

$4\cdot0+2\cdot14=28$

$\text{mgm}(2,4)=4$

$4\cdot0+2\cdot14+4n-4n=28$

$4\cdot0+4\cdot n+2\cdot14-2\cdot 2n=28$

$4n+2(14-2n)=28$

Och alltså får vi att $x=n$ och $y=14-2n$ där $n\in\mathbb{Z}$.

AlvinB skrev:

Laguna skrev:

Visa föregående citat

Andersson_4 skrev:

Det är när jag ska hitta de resterande lösningarna som jag stöter på problem. 

Det är den enkla delen. Om vi har ax1 + by1 = c, så gäller att x2 = x1+b, y2 = y1-a är en ny lösning, eftersom a*b + b*(-a) = 0.

Fast om du använder $a\cdot b$ och $-a\cdot b$ kommer du att missa lösningar. I detta fall får du enligt din metod att nästa lösning ligger vid $x=0+2=2$ och $y=14-4=10$, men det finns faktiskt en lösning $x=1$, $y=12$ däremellan.

Det är därför viktigt att istället för att addera och subtrahera $a\cdot b$ så adderar vi och subtraherar vi $\text{mgm}(a,b)$ eftersom vi då inte missar några lösningar. Jag gillar att ställa upp det så här:

$4\cdot0+2\cdot14=28$

$\text{mgm}(2,4)=4$

$4\cdot0+2\cdot14+4n-4n=28$

$4\cdot0+4\cdot n+2\cdot14-2\cdot 2n=28$

$4n+2(14-2n)=28$

Och alltså får vi att $x=n$ och $y=14-2n$ där $n\in\mathbb{Z}$.

Ja, jag tänkte inte på att minsta gemensamma faktorn inte var 1 här. Delar med den är förstås det första man gör.