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

Modular algorithm question

  1. Feb 28, 2008 #1
    how can i solve this problem?

    [ x1= a (mod 100) , a= 20 (mod 37) ]

    [ x2= b (mod 100) , b= 15 (mod 37) ]

    [ x3= c (mod 100) , c= 18 (mod 37) ]

    must be ; x2= a.k + y (mod100)


    x3= b.k + y (mod100)

    i need find b and c.. thank you best regards..
  2. jcsd
  3. Feb 28, 2008 #2


    User Avatar
    Science Advisor

    Looks to me like "Chinese remainder theorem". In any case, it is certainly not "Calculus and Analysis. I am moving this to the number theory forum.
  4. Feb 29, 2008 #3


    User Avatar
    Science Advisor
    Homework Helper

    Are these the same y and k, the same y, but some arbitrary k, or what?
  5. Mar 8, 2008 #4
    yes same y and k
  6. Mar 8, 2008 #5
    booney1983: yes same y and k

    That's not especially helpful since no effort to define them was given. As for y I see that you use it in the two final equations. So I am wondering if it could not simply be dropped and is meaningless?

    What is b.k? I have guessed it means b times k. The symbol "*" is sometimes used for multiplication. Maybe some countries think differently.
    Last edited: Mar 9, 2008
  7. Mar 9, 2008 #6


    User Avatar
    Science Advisor
    Homework Helper

    Here's how I'm interpreting the question:

    Find b and c such that the following equations are satisfied in terms of the other variables.
    1. [tex]x_1\equiv a\pmod{100}[/tex]
    2. [tex]a\equiv20\pmod{37}[/tex]
    3. [tex]x_2\equiv b\pmod{100}[/tex]
    4. [tex]b\equiv15\pmod{37}[/tex]
    5. [tex]x_3\equiv c\pmod{100}[/tex]
    6. [tex]c\equiv18\pmod{37}[/tex]
    7. [tex]x_2\equiv a\cdot k+y\pmod{100}[/tex]
    8. [tex]x_3\equiv b\cdot k+y\pmod{100}[/tex]

    It's trivial to determine the values of b and c mod 100: [itex]b\equiv ak+y[/itex], [itex]c\equiv bk+y[/itex]. The CRT could then be used to determine b and c mod 3700.
    Last edited: Mar 9, 2008
  8. Mar 10, 2008 #7
    One simple solution is X1=X2=X3=18 Mod 100. a=2018, b=718, c=18. k=1, y=0. which renders the last two equations redundant, while 5 and 6 are taken care of since X3=c.
    Last edited: Mar 10, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook