Modulus functions

Oct 2008
29
0
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.
 
Nov 2009
485
184
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}\).
 
  • Like
Reactions: Mathsnewbie
Oct 2008
29
0
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.
 
Mar 2010
1,055
290
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
 
  • Like
Reactions: Mathsnewbie