Diofantisk ekvation och Euklides algoritm baklänges
Hej,
Jag stötte på en uppgift som involverar en diofantisk ekvation och användningen av Euklides algoritm baklänges. Jag skulle uppskatta om någon kunde hjälpa mig att förstå både uppgiften och lösningen bättre.
Uppgiften: Rolf köper godis för 620 kr till priser i en tävling. Godiset finns antingen i 250 grams lådor som kostar 50 kronor och 100 grams lådor som kostar 20 kronor. Hur många lådor av varje storlek kan han ha köpt?
Lösningen: Problemet formuleras som en diofantisk ekvation: $50x + 20y = 620$. Sedan används Euklides algoritm, och jag följer med tills största gemensamma delaren är 1. Men jag står fast vid det här steget: "Multiplicera med 62: $62 = 5 \cdot 62 + 2 \cdot (-124)$."
Jag skulle även vilja ha hjälp med att förstå varför de multiplicerar ekvationen med 62 och hur de kommer fram till koefficienterna -2k och 5k för $x$ och $y$. Varför är det just -2k och 5k? 
Om du söker efter "euklides baklänges" här på pluggakuten hittar du en del om det.
För att använda TEX här får man skriva dubbla dollartecken.
Laguna skrev:Om du söker efter "euklides baklänges" här på pluggakuten hittar du en del om det.
För att använda TEX här får man skriva dubbla dollartecken.
Varför multiplicerar de ekvationen med 62, och hur kommer de fram till koefficienterna -2k och 5k för och . Varför är det just -2k och 5k?
Om ax + by = c har en lösning x = m och y = n, så är x = m+kb och y = n-ka också en lösning.
Laguna skrev:Om ax + by = c har en lösning x = m och y = n
Så vi har där (m), och (n)
så är x = m+kb
62 = 62 + 2k
och y = n-ka också en lösning.
-124 = -124 - 5k
Så?
