# Modulus functions

• May 16th 2010, 03:58 PM
Mathsnewbie
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.
• May 16th 2010, 04:56 PM
roninpro
I'm not sure what the problem is. You have $34u\equiv 33\pmod{41}$. Multiply both sides by 5 to find $u\equiv 15\pmod{41}$. Then, $u=41v+15$ and $x=34(41v+15)+15=1394v+525$. In summary, any solution to the system has the form $x\equiv 525\pmod{1394}$.
• May 17th 2010, 02:59 AM
Mathsnewbie
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
hollywood
FYI, the Chinese Remainder Theorem gives a method for solving a set of congruences of the form $x\equiv{a_i}\ (\text{mod }m_i)$, where the $m_i$ 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 $34x\equiv{1}\ (\text{mod }41)$. 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