How Do I Obtain Specific Solutions for Linear Diophantine Equations?

[totoro]

i need help with this question

893x=266(mod 2432) ,= mean congruence

fisrt i find gcd(893,2432)=19
then i need to find u,v for 893u-2432v=19
the u and v i found is -49 and -18
but the answer here in my book is 79 and 29
after calculating, i found that both the answer are correct. my question is how to get 79 and 29?


thanks.

 

[HallsofIvy]

If the problem is "893x=266(mod 2432)"

how could the answer be "u= 79 and v= 29" OR "u= -49 and v= -18"?

Where did u and v come from? What happened to x?

 

[totoro]

first i use this method to find the gcd of (893,2432).that is
2432=893(2)+646
893=646(1)+247
646=247(2)+152
247=152(1)+95
152=95(1)+57
95=57(1)+38
57=38(1)+19
38=19(2)+0
from here i found the gcd is 19
then 19 can divide 266, therefor it has a solution

if i reverse all the step above, i will get
2432(18)-893(49)=19
from this 893x=266(mod2432)i can change to 893x-2432y=266
therefor this formula 893(-49)-2432(-18)=19 should multiply by 14 to get the formula same as above. with this i can get x later, but the problem is that i get -49 and -18 and not 79 and 29.

 

[arcnets]

totoro,
I think the answer in the book is wrong. Because
<br /> 893\cdot79=19(\mod{2432})<br />
<br /> 893\cdot29=1577(\mod{2432})<br />
They do not work. Why do you think they are correct?

(Why does it make these spaces before mod? How can I TeX it better?)

 

[totoro]

the formula i get is 893u - 2432v = 19. with euclidean algorithm i get 893(-49) - 2432(-18) = 19. i get negative numbers (u,v) = (-49,-18). how can i change it to a positive numbers like (u,v) = (79,29)?

 

[arcnets]

Sorry, I can only help you if you answer my question.