# Modulus functions

#### Mathsnewbie

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.

#### roninpro

I'm not sure what the problem is. You have $$\displaystyle 34u\equiv 33\pmod{41}$$. Multiply both sides by 5 to find $$\displaystyle u\equiv 15\pmod{41}$$. Then, $$\displaystyle u=41v+15$$ and $$\displaystyle x=34(41v+15)+15=1394v+525$$. In summary, any solution to the system has the form $$\displaystyle x\equiv 525\pmod{1394}$$.

• Mathsnewbie

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

#### hollywood

FYI, the Chinese Remainder Theorem gives a method for solving a set of congruences of the form $$\displaystyle x\equiv{a_i}\ (\text{mod }m_i)$$, where the $$\displaystyle 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 $$\displaystyle 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

• Mathsnewbie