How to solve simultaneous congruence 3x= 14 mod 17, 7x= 13 mod 31

[andrey21]

Solve the following simultaneous congruence

3x= 14 mod 17

7x= 13 mod 31


My attempt

I have no problems solving when in the form:

x= 2 mod 13

x= 4 mod 27

for example but am confused by the above question, any help would be great.

 

[kru_]

Well,
3x \equiv 14 mod 17 \Rightarrow 17 \mid (3x - 14) \Rightarrow 17n = 3x - 14 \Rightarrow x = \frac{17n+14}{3}
7x \equiv 13 mod 31 \Rightarrow 31 \mid (7x - 13) \Rightarrow 31m = 7x - 13 \Rightarrow x = \frac{31m + 13}{7}

Basically, we need to find values of x such that x = \frac{31m + 13}{7} = \frac{17n+14}{3}

Solving for n or m should give you a line of values that will work.

 

[andrey21]

Sorry I am still a little confused, solving for m I obtained:

31m = 7x-13 = 17n + 14 / 3

 

[HallsofIvy]

To solve 3x= 14 mod 17, you need to "divide" by 3- you need to find "1/3" in mod 17 which means you want to solve 3x= 1 mod 17. For this simple problem, you can note that 3(6)= 18 mod 17 so that x= 6 mod 17. For a more algorithmic method (specifically, using the Euclidean division algorithm) note that 3x= 1 mod 17 means that 3x= 1+ 17y which is the same as 3x- 17y= 1, a Diophantine equation. 3 divides into 17 5 times with remainder 2: 17(1)- 3(5)= 2. Further 2 divides into 3 once with remainder 1: 3- 2= 1. Replacing the "2" in that equation with the "17(1)- 3(5)" we have 3- (17(1)- 3(5))= 3(6)- 17(1)= 1. So x= 6 is a solution: 6 is "1/3" mod 17 (6(3)= 18= 1 mod 17)

Once we have that x= 14/3= 14(6)= 84= 16 mod 17 satisfies your first equation.

Similarly, to solve 7x= 13 mod 31, first solve 7x= 1 mod 31. That means that 7x= 1+ 31y or 7x- 31y= 1. 7 divides into 31 4 times with remainder 3: 31- 4(7)= 3. 3 divides into 7 twice with remainder 1: 7- 2(3)= 1. Replacing the "3" in that by 31- 4(7) we have 7- 2(31- 4(7)= 7(9)- 2(31) xo x= 9 is a solution: "1/7" is 9 mod 31. From that x= 13/7= 13(9)= 24 mod 31.

Your two equations are equivalent to x= 16 mod 17 and x= 24 mod 31 which you say you can solve.