Största gemensamma delare med linjärkombination

Hej Varren97 och välkommen till PluggAkuten,

Uppgiften är att lösa den diofantiska ekvationen

$7=231m+1820n$

Förmodligen har ni fått lära er någon metod för att lösa diofantiska ekvationer. Nedan ger jag ett förslag på lösningsgång, men det kan hända att det är lite för "formellt" för just din kurs.

Ekvationen har lösningar eftersom $\mathrm{sgd}(1820,231)|7$. Den allmänna lösningen till ekvationen ges av

$m=m_0+\frac{1820}{\mathrm{sgd}(231,1820)}\cdot k$

$n=n_0-\frac{231}{\mathrm{sgd}(231,1820)}\cdot k$

För att hitta en partikulärlösning ($m_0, n_0$) kan det vara enklast att dela ekvationen med 7

$33m+260n=1$

Att hitta en partikulärlösning ($m_0, n_0$) till denna ekvation kan man t.ex. göra genom att köra euklides algortim först framlänges och sedan baklänges.

$260=33\cdot7+29$

$33=29\cdot1+4$

$29=4\cdot7+1$

$1=29-4\cdot7=29-7(33-29)=8\cdot 29- 7\cdot 33=$

$=8(260-33\cdot 7)-7\cdot 33=8\cdot260-63\cdot33$

En partikulärlösning är alltså $n_0=8, m_0=-63$. Den allmänna lösningen ges av

$n=8-33\cdot k,\quad m=-63+260\cdot k, \quad k\in\mathbb{Z}$

Här är en graph till Guggles lösning, där du kan byta k till olika heltal och se alla möjliga partikulära lösningar: