Hi, I've got so far try to solve simultaneous congruence equations but have run a ground.
Question is solve the simultaneous equations
7x = 3mod34 and x=7mod41
I've solved the first one to get x= 15mod 34 hence x= 34u+15
The second is x= 7 mod 41
Thus I've put 34u+15 = 7mod 41
Now at this point I thought it would go to 34u = 33mod41 but if this is the case then I'm struggling to solve for u. I think I've made a mistake at 34u+15 = 7 mod 41 but not sure what.
May 16th 2010, 04:56 PM
I'm not sure what the problem is. You have . Multiply both sides by 5 to find . Then, and . In summary, any solution to the system has the form .
May 17th 2010, 02:59 AM
I'm a bit confused on the middle step, how did you get to u=15mod41?
I don't understand how you figured out to multiply it by 5.
May 17th 2010, 11:29 PM
FYI, the Chinese Remainder Theorem gives a method for solving a set of congruences of the form , where the are pairwise relatively prime.
Your solution is probably just as easy though.
The number 5 that roninpro used should be the inverse (mod 41) of 34. In other words, it is the solution to . I believe this is 35, not 5. 5 is the inverse of 33, not 34. The Extended Euclidean Algorithm can find this inverse if the numbers are larger and brute force is too hard.
So u=35*33=7 (mod 41), and x=34(41v+7)+15=1394v+253, or x=253 (mod 1394).