Thread: Modulus functions

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.

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 .

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.

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).

As a check,
7*253=1771=3 (mod 34)
253=7 (mod 41)

- Hollywood