Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Mean congruence homework

  1. Nov 29, 2003 #1
    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.
     
  2. jcsd
  3. Nov 29, 2003 #2

    HallsofIvy

    User Avatar
    Science Advisor

    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?
     
  4. Nov 29, 2003 #3
    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.
     
  5. Nov 29, 2003 #4
    totoro,
    I think the answer in the book is wrong. Because
    [tex]
    893\cdot79=19(\mod{2432})
    [/tex]
    [tex]
    893\cdot29=1577(\mod{2432})
    [/tex]
    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?)
     
    Last edited: Nov 29, 2003
  6. Nov 29, 2003 #5
    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)?
     
  7. Nov 30, 2003 #6
    Sorry, I can only help you if you answer my question.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook