Simultaneous Modulus CongruenciesDate: 04/18/2001 at 03:11:48 From: Ooi Chin Wah Subject: Number theory Thanks for your answers to the questions that I asked earlier. I would be very grateful if you can help me again. Solve x = 3 (mod 8), x = 11 (mod 20) and x = 1 (mod 15). Thanks. Date: 04/18/2001 at 10:01:54 From: Doctor Rob Subject: Re: Number theory Thanks for writing back to Ask Dr. Math. This is equivalent to solving the following congruencies with prime-power moduli: x = 3 (mod 8) x = 11 = 3 (mod 4) x = 11 = 1 (mod 5) x = 1 (mod 3) x = 1 (mod 5) Notice that the second and fifth congruencies are redundant, so you are reduced to solving: x = 3 (mod 8) x = 1 (mod 3) x = 1 (mod 5) The last two are easily combined to get: x = 3 (mod 8) x = 1 (mod 15) Now use the fact that: 2*8 + (-1)*15 = 1 to conclude that: 15^(-1) = -1 = 7 (mod 8) 8^(-1) = 2 (mod 15) Now you are ready to use the Chinese Remainder Theorem. I leave the rest to you. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/