Hjälp en hjärnfattig att förstå diophantism, så stackarn kan fiska alldeles själv i framtiden.

Nu har 24 timmar gått, så jag lyfter upp skamlös min tråd.

Angående mina frågor:

1. Den första gå uppenbarligen inte att lösa. Varför? -> det tror jag beror på att resultatet måste vara delbart också av SGD (jag har en känsla om varför men det sitter inte fast skruvad)

2. Varför den första steg är alltid att dela med SGD? Vad är poängen? -> det är nog en förenkling men hur funkar SGD är inte fastskruvad som sagt...

3. När jag har hittat den ena lösning, hur gör jag för att hitta de andra lösningarna? -> det har jag sett i klassrummet idag, men det känns lite dimmig fortfarande. Jag läser gärna en enkelt förtydligande.

Däremot har jag hunnit fatta att båda x och y bildar en aritmetisk följd. Dessutom är x och y koordinat av en punkt med heltals koordinat och kan representeras grafisk... Enligt kurslitteratur lösning till en diophantisk ekvation är egentligen:

$\left\{\begin{array}{l}{x}_0+an\\ y_0-bn\end{array}\right.$

men a är relaterad till y-axeln, när b är relaterad till x-axeln. Varför?

Om du skriver ner lite värden för vänsterledet i a) för olika x och y så kommer du att upptäcka att de alla är multipler av 7. Men högerledet ligger inte i 7ans gångertabell. 

1. Kan man t.ex. på följande sätt visa, att den inte går att lösa:

$$\begin{gathered} 14x-21y=333 \\ y=\frac{14x}{21}-\frac{333}{21}=\frac{14x}{21}-\frac{18}{21}-15 \end{gathered}$$

Man kan leta efter heltals-lösningar för y och kan t.ex. börja med:

$x_1=\frac{18}{14}$
Då finns det också ett gäng (n) andra heltals-lösningar för y som t.ex:

$x_n=n\frac{21}{14}+\frac{18}{14}=n\frac{3}{2}+\frac{9}{7}$....n är också ett heltal...men $x_n$ kan aldrig bli det.

Vilket skulle visas....

dajamanté skrev :

1. Den första gå uppenbarligen inte att lösa. Varför? -> det tror jag beror på att resultatet måste vara delbart också av SGD (jag har en känsla om varför men det sitter inte fast skruvad)

Om SGD(a,b) inte delar c i ax+by=c så saknar ekvationen heltalslösningar.  I ditt exempel SGD(14,21)=7. 7 delar inte 333, alltså saknar ekvationen lösningar. Hade SGD(a,b)=1 så finns det ALLTID lösningar eftersom 1 delar alla c.

2. Varför den första steg är alltid att dela med SGD? Vad är poängen? -> det är nog en förenkling men hur funkar SGD är inte fastskruvad som sagt...

Man beräknar alltid SGD för att få veta om det finns lösningar, se mitt var på din första fråga.

 I regel delar man sedan ekvationen med SGD för att få en ny enklare ekvation med SGD(a',b')=1. (men man behöver inte göra det). Det viktiga är du kommer ihåg om du gjort det eller inte för att avgöra om du behöver skala om svaret. Detta gäller också om du löst hjälpekvationen ax+by=1 istället för ax+by=c).

Dessutom kan man ha nytta av SGDn när man ska hitta en partikulärlösning, t.ex. om du kör Euklides baklänges.

3. När jag har hittat den ena lösning, hur gör jag för att hitta de andra lösningarna? -> det har jag sett i klassrummet idag, men det känns lite dimmig fortfarande. Jag läser gärna en enkelt förtydligande.

Lösningarna ges alltid av en partikulärlösning $x_0, y_0$ + de homogena lösningarna. Lösningarna till ax+by=c där SGD(a,b)|c blir alltid

$x=x_0+\frac{bn}{SGD(a,b)}$

$y=y_0-\frac{an}{SGD(a,b)}$

Om du vill kan du switcha tecknet framför an och bn (eftersom $n\in \mathbb{Z}$). Ibland väljer man att förkorta sin ekvation med SGD(a,b) redan i första skedet (se min kommentar ovan). Då behöver man inte dela de homogena lösningarna med SGD(a,b). T.ex. har ekvationen $ax+by=c$, med SGD(a,b)=1 lösningarna (och jag byter medvetet tecken bara för att visa att man får göra så, bara man gör det i båda ekvationerna samtidigt):

$x=x_0-bn$

$y=y_0+an$

Tack till båda för svaren!

@Affe: varför $x_n=\frac{18}{14}+n\frac{\mathbf{21}}{\mathbf{14}}$ ? 21 måste annulera 21 i nämnaren för $-\frac{18}{21}$, men vad är 14 för?

@Guggle: vi fick förklaring att 

$\left\{\begin{array}{l}{x}_0+an\\ y_0-bn\end{array}\right.$ men inte $\left\{\begin{array}{l}{x}_0+\frac{an}{SGD(a,b)}\\ y_0-\frac{bn}{SGD(a,b)}\end{array}\right.$

Jag har försökt applicera det och lösa $114x+303y=168$ utan att skala ner först.

$$\begin{gathered} 303=2*114 + 75 \\ 114=1*75+39 \\ 75=1*39+36 \\ 39=1*36+3 \\ 36=12*3 + 0 \end{gathered}$$

SGD är nu 3 men vi skalar inte ner.

Så baklänges blir det:

$$\begin{gathered} 75=303-2*114 \\ 39=114-75 \\ 36=75-39 \\ 3= 39-36 \end{gathered}$$

Detta ger:

$$\begin{gathered} 3=39-36 \\ =39-(75-39)=2*39-75 \\ =2*(114-75)-75 \\ =2*114-2*75-75=2*114-3*75 \\ =2*114-3*(303-2*114) \\ =2*114-3*303+6*114=8*114-3*303 \end{gathered}$$

Problem: det ger mig 3 som svar, alltså SGD, och inte 168. Jag har kollat två gånger för slarv (med miniräknare) och jag hittar inte tyvärr :(. Vad är det som pågår?

dajamanté skrev :

Detta ger:

$$\begin{gathered} 3=39-36 \\ =39-(75-39)=2*39-75 \\ =2*(114-75)-75 \\ =2*114-2*75-75=2*114-3*75 \\ =2*114-3*(303-2*114) \\ =2*114-3*303+6*114=8*114-3*303 \end{gathered}$$

 

Problem: det ger mig 3 som svar, alltså SGD, och inte 168. Jag har kollat två gånger för slarv (med miniräknare) och jag hittar inte tyvärr :(. Vad är det som pågår?

Jättebra! Du har räknat rätt och fått en lösning till ekvationen 114x'+303y'=3 (x'=8, y'=-3). Hade du istället delat med SGD(114,303) hade du fått ekvationen 38x'+101y'=1 av resultatet eftersom euklides baklänges bygger på att du löser ut SGD :)

Du har alltså hittat en partikulärlösning till 114x'+303y'=3. Nu kan vi multiplicera BÅDA sidor (alltså lösningarna på vänster sida och talet 3 på höger sida) med ett tal så att vi får vår ursprungliga ekvation 114x+303y=168 . Kan du lista ut vilket tal du ska multiplicera med? Vad blir alltså $x_0$ och $y_0$?

Slutligen är lösningarna

$x=x0+303n/SGD(114,303)$

$y=y0-114n/SGD(114,303)$.

Eftersom jag måste multiplicera båda lösningarna, det blir nog

$x=x_0*3$ dvs $x= 8*3=24$ och $y=y_0*3$ dvs $y=-3*3=-9$ .. som blir mycket riktigt 9. 

Sorry, nej, jag förstår inte hur jag kan hitta 168!

Du har hittat en partikulärlösning $\bar{x}=8,\ \bar{y}=-3$ till ekvationen

$114\bar{x}+303\bar{y}=3$

Om vi multiplicerar båda led med 56 får vi

$114\underbrace{(\bar{x}\cdot56)}_{x_0}+303\underbrace{(\bar{y}\cdot 56)}_{y_0}=168$

Vilket är misstänkt likt den ekvation vi vill hitta en partikulärlösning till $114x+303y=168$

Kan du nu klura ut $x_0$ och $y_0$ samt den allmänna lösningen?

dajamanté skrev :

Tack till båda för svaren!

@Affe: varför $x_n=\frac{18}{14}+n\frac{\mathbf{21}}{\mathbf{14}}$ ? 21 måste annulera 21 i nämnaren för $-\frac{18}{21}$, men vad är 14 för?

 $$\begin{gathered} f\left(x\right)=\frac{14x}{21}-\frac{18}{21}-15 \\ f\left(\frac{18}{14}\right)=\frac{18}{21}-\frac{18}{21}-15 \end{gathered}$$

@Guggle: vi fick förklaring att 

$\left\{\begin{array}{l}{x}_0+an\\ y_0-bn\end{array}\right.$ men inte $\left\{\begin{array}{l}{x}_0+\frac{an}{SGD(a,b)}\\ y_0-\frac{bn}{SGD(a,b)}\end{array}\right.$

Jag har försökt applicera det och lösa $114x+303y=168$ utan att skala ner först.

$$\begin{gathered} 303=2*114+75 \\ 114=1*75+39 \\ 75=1*39+36 \\ 39=1*36+3 \\ 36=12*3+0 \end{gathered}$$

SGD är nu 3 men vi skalar inte ner.

Så baklänges blir det:

$$\begin{gathered} 75=303-2*114 \\ 39=114-75 \\ 36=75-39 \\ 3=39-36 \end{gathered}$$

Detta ger:

$$\begin{gathered} 3=39-36 \\ =39-(75-39)=2*39-75 \\ =2*(114-75)-75 \\ =2*114-2*75-75=2*114-3*75 \\ =2*114-3*(303-2*114) \\ =2*114-3*303+6*114=8*114-3*303 \end{gathered}$$

 

Problem: det ger mig 3 som svar, alltså SGD, och inte 168. Jag har kollat två gånger för slarv (med miniräknare) och jag hittar inte tyvärr :(. Vad är det som pågår?

Kolla efter @Affe i mitt föregående inlägg

Affe Jkpg skrev :

Kolla efter @Affe i mitt föregående inlägg

Yes, tack! Nu har jag sett!

Guggle skrev :

Du har hittat en partikulärlösning $\bar{x}=8,\ \bar{y}=-3$ till ekvationen

$114\bar{x}+303\bar{y}=3$

Om vi multiplicerar båda led med 56 får vi

$114\underbrace{(\bar{x}\cdot56)}_{x_0}+303\underbrace{(\bar{y}\cdot 56)}_{y_0}=168$

Vilket är misstänkt likt den ekvation vi vill hitta en partikulärlösning till $114x+303y=168$

Kan du nu klura ut $x_0$ och $y_0$ samt den allmänna lösningen?

Kan det råka bli $56 \cdot 8$ dvs 448 och $56 \cdot -3$ dvs -168?

dajamanté skrev :

Kan det råka bli $56 \cdot 8$ dvs 448 och $56 \cdot -3$ dvs -168?

Ja, just det, $x_0=448$ och $y_0=-168$ är en partikulärlösning till din ursprungliga ekvation. Men det är inte färdigt, du vill ha fram _alla_ lösningar, inte bara en enda ynklig partikulärlösning!

...ok så jag råkar veta att min lösning kommer i form av:

$$\begin{gathered} \left\{\begin{array}{l}{x}_0-\frac{an}{SGD(x_0,y_0)}\\ y_0+\frac{bn}{SGD(x_0,y_0)}\end{array}\right. \\ \left\{\begin{array}{l}448-\frac{an}{SGD(448,-168)}\\ -168+\frac{bn}{SGD(448,-168)}\end{array}\right. \\ \left\{\begin{array}{l}448-\frac{an}{3}\\ -168+\frac{bn}{3}\end{array}\right. \end{gathered}$$

... men a och b förbli mysteriösa för mig. Jag vet att det är tal som gör att lösningarna sitter på linjen men tyvärr har jag inte tillräcklig men RAM för att förstå vad det är som jag måste beräkna...

dajamanté skrev :

... men a och b förbli mysteriösa för mig. Jag vet att det är tal som gör att lösningarna sitter på linjen men tyvärr har jag inte tillräcklig men RAM för att förstå vad det är som jag måste beräkna...

Ekvationen $ax+by=c$, där SGD(a,b)|c har lösningarna

$x=x_0+\frac{b\cdot n}{SGD(a,b)}$

$y=y_0-\frac{a\cdot n}{SGD(a,b)}$

Du har ekvationen $114x+303y=168$. Om du jämför den med ekvationen ovan, kan du se några likheter och lista ut a, b och c? Ledtråd: c=168, det är mycket enklare att du tror!

(och ja, $ax+by=c$ är en rät linje och  ja, man hittar lösningarna på linjen, men nu vill vi bara veta konstanterna a och b)

Jag har stirrat på skärmen ganska länge i hoppet för en inre belysning.

Men nej. 

Till slut gick jag tillbaka till dina andra meddelande:

Guggle skrev :

Slutligen är lösningarna

$x=x0+303n/SGD(114,303)$

$y=y0-114n/SGD(114,303)$.

$x=x0+101n$

$y=y0-38n$

Är det det? 

Ja, nu blev det ju lite fusk, men

$x=448+101n$

$y=-168-38n$

Så för att sammanfatta. Du har ekvationen $ax+by=c$, i just det här fallet $114x+303y=167$. Alltså är a=114, b=303 och c=168.

1. Du beräknar SGD(a,b) och kollar om det delar c. I just det här fallet SGD(114,303)=3, och 3|168 (168/3=56). Alltså finns det heltalslösningar.

2. Du beräknar en partikulärlösning till en hjälpekvation genom Euklides baklänges, din hjälpekvation var 114x+303y=3. Du skalar upp lösningen och konstaterar att en partikulärlösning till din "riktiga" ekvation är $x_0=448$ och $y_0=-168$. I det här steget är det viktigt att du håller ordning på vilken ekvation du faktiskt löst. Delar du med 3 redan  från början kommer du lösa hjälpekvationen $38x+101y=1$ istället samt ha ekvationen $38x+101y=56$ som "riktig" ekvation.

3. Slutligen skriver du ned alla lösningar som en partikulärlösning + de homogena lösningarna enligt formeln där du använder a och b från din "riktiga" ekvation.

Guggle skrev :

Ja, nu blev det ju lite fusk, men

$x=448+101n$

$y=-168-38n$

Ja, jag ber om ursäkt. Men det blev riktigt långt skärmstirrande utan resultat.

3. Slutligen skriver du ned alla lösningar som en partikulärlösning + de homogena lösningarna enligt formeln där du använder a och b från din "riktiga" ekvation.

Du menar nu a och b från min riktiga ekvation delade med SGD?

Och varför fungerar det överhuvudtaket? Jag har noll intuition för det.

dajamanté skrev :

Guggle skrev :

3. Slutligen skriver du ned alla lösningar som en partikulärlösning + de homogena lösningarna enligt formeln där du använder a och b från din "riktiga" ekvation.

Du menar nu a och b från min riktiga ekvation delade med SGD?

Ja!

$\underbrace{114}_a x+\underbrace{303}_b y=\underbrace{168}_c$

a=114, b=303, c=168

SGD(114,303)=3, och enligt den allmänna formeln ska du alltså dela a och b med 3 när du anger lösningarna.

Man kan också dela hela ekvationen med 3 redan från början för att få en enklare ekvation att jobba med. Då får vi

$\underbrace{38}_a x+\underbrace{101}_b y=\underbrace{56}_c$

a=38, b=101, c=56

Notera nu att SGD(38,101)=1. Alltså ska vi dela a och b med 1 istället för 3 (dvs vi kan strunta i det). Skillnaden här är att du hittar partikulörlösningar till 38x+101x=1 och sedan skala upp det till 38x+101x=56. Lösningarna blir samma.

Och varför fungerar det överhuvudtaket? Jag har noll intuition för det.

Varför den euklidiska algoritmen fungerar eller varför man får slå ihop de homogena lösningarna med partikulärlösningen eller något annat? :)

Allt kan verka lite krångligt och förvirrande i början men det är egentligen bara tre enkla steg att hålla reda på, när du räknat igenom några diofantiska ekvationer kommer det klarna, jag lovar!

Haha jo, allt känns krångligt:

Guggle skrev :

Varför den euklidiska algoritmen fungerar eller varför man får slå ihop de homogena lösningarna med partikulärlösningen eller något annat? :)

Isf frågan var varför får slå ihop de homogena lösningarna med de partikulära :)

Jag har kollat en geometrisk förkläring för Euklides algoritm, och det börjar att landa.