Citat:
Ursprungligen postat av
mjoxmux
Hej!
Jag skulle vilja få hjälp med att se om jag räknat rätt eller ej i min diofantiska ekvation. Jag tycker det verkar korrekt men överensstämmer inte med facit.
34x + 28y = 8
Vi ser att man kan förkorta med 2.
17x +14y = 4
Sgd(34,28) = 2
Euklides algoritm:
sgd(17,14)
17 = 1 * 14 +3
14 = 4 * 3 +2
3 = 1 * 2 +1
Bezouts identitet:
1 = 3 - 1 * 2
1 = 3 - 1 * ( 14 - 4 * 3)
1 = 5 * 3 - 1 * 14
1 = 5 * (17 - 14) - 1 * 14
1 = 5 * 17 - 6 * 14
Vi ser att 5 = u och -6 = v
Nu multiplicerar vi med 4, då c = 4.
4 = 5 * 4 * 17 - 6 * 4 * 14
4 = 20 * 17 - 24 * 14
20 = cu, -24 = cv
Nu kan vi formulera fram den allmänna lösningen som ska vara (x,y) = (cu - bn, cv + an)
alltså : (x,y) = (20 - 14n, -24 + 17n)
Vad gör jag fel?
Facit säger: (x,y) = ( 6 - 14n, -7 + 14n)
Tacksam för svar!
Det fet-kursiva är ju samma
17x +14y = 4
Euklides algoritm:
sgd(17,14)
17 = 1 * 14 +3
14 = 4 * 3 +2
3 = 1 * 2 +1
Jag döper 17x till a, 14y till b
alltså
a = 1*b +3 <-> b = a-3 <-> 3=a-b
vilket ger
a-3 = 4*(a-b) + 2
a-3 = 4a-4b+2 <-> 2 = 4b-3a-3
det ger
a-b = 1*(4b-3a-3) + 1
a-b = 4b-3a-2
ger
5b -4a = 2
Nu sökte vi ju en lösning till 4, alltså måste vi multiplicera med 2.
10b -8a = 4
Vårt x0 är alltså -8, och vårt y0 10
Alla lösningar fås genom
x = x0 +(b/d)*n där d=sgd(34,28)
y = y0 -(a/d)*n
x = -4 +(28/2)*n = -8 +14n
y = 10 -(34/2)*n = 10 -17n
sätter in n=1 i både x och y, vilket ger
x = -8 +14*1 =
6+14n
y = 10 -17*1 =
-7-17n