Citat:
Ursprungligen postat av
ZethMalkovi
Skulle uppskatta hjälp med denna diofantiska ekvation
17x+67y=250
Euklides algoritm
67=17*3+16
16=3*5+1
5=1*5+0
1=16-3*5=(67-17*3)-3*5
sen då??
17x+67y=250
67y=250-17x
y=250/67-17x/67
sätt nu x=67t och vi får
y=250/67-17t
x=67t
Vi har riktningsvektorn som heltal men vi söker en punkt på linjen som också är heltal så vi med hjälp av riktningsvektorn kan "hoppa" mellan heltalen. Vi använder euklides algoritm för att hitta en lösning.
67=3*17+16 (1)
17=1*16+1 (2)
16=16*1+0 (3)
67 och 17 är alltså relativt prima eftersom deras sgd är 1. Detta betyder att det finns två heltal x och y sådana att 17x+67y=1 vi kan hitta dessa genom att använda algoritmen baklänges.
(1) --> 16= 67-3*17
(2) --> 1=17-1*16
kombinerar (1) och (2) --> 1=17-1*(67-3*17)=17-67+3*17=17*
4+67*
-1. Vi har nu hittat våra x och y. Multiplicera båda leden med 250
250=17*(4*250)+67*(250*-1)=17*
1000+67*
-250. Vi har nu hittat våran "heltalspunkt".
x=1000+67t
y=-250-17t