Diofantisk ekvation
"Bestäm ev. heltalslösningar till ekvationen 5x+31y=1"
sgd (5, 31) = 1
1*1=1 , ok!
Längre än så kommer jag inte, eftersom jag måste dela 5x+31y med 1, och använda Euklides algoritm igen, vilket bara kommer ge samma svar, dvs 1.
Hur ser det ut när du använda Euklides algoritm, du går bara baklänges i den för att få fram en lösning till ekvationen.
Det är ju inte heller speciellt svårt att gissa sig till en lösning.
sgd (5,31)
31 = 6*5 + 1
6 = 5*1+1
5=1*5
Inte för att det direkt var nödvändigt att använda Euklides här men... hur menar du med baklänges?
Och ja, det är lätt att se att en lösning skulle kunna vara x = -6 + 31n och y = 1 - 5n
Ja du är ju egentligen färdig vid
31 = 6*5 + 1
Eftersom du kommit till resten 1. Så detta blir ju inte speciellt bra exempel, men iaf, baklänges blir det
1 = 31 - 6*5
Så då ser man att en lösning är y = 1, x = -6, vilket ger att alla lösningar är
x = -6 + 31n
y = 1 - 5n
Ah, just det! Tack!
