How do I solve simultaneous congruence modulo equations

Question

How do I find one value of $x$ in these equations? $$ \begin{cases} x \equiv 3 \pmod{5}\\ x \equiv 4 \pmod{7} \end{cases} $$

Answer 1

First ascertain that the moduli are coprime, guaranteeing a solution by the CRT.

Then solve one equation first (doesn't matter which):

$x \equiv 4 \pmod 7$

$x = 7k + 4$

Substitute this into second equation.

$7k + 4 \equiv 3 \pmod 5$

$7k \equiv -1 \pmod 5$

$k \equiv (-1)(7^{-1}) \pmod 5$

$7^{-1}$ is not a reciprocal. It is the modular multiplicative inverse of $7$. You can find it using the Extended Euclidean Algorithm, but for small moduli, it's much easier to just test a few values. In this case, the inverse is $3$ because $(7)(3) = 21 \equiv 1 \pmod 5$.

So $k \equiv (-1)(3) \pmod 5 \equiv 2 \pmod 5$

$k = 5t + 2$.

Substitute that back into the solution of the original equation:

$x = 7k + 4 = 7(5t+2) + 4 = 35t + 18$

which is the required solution. If you want to express it more compactly, you can write:

$x \equiv 18 \pmod{35}$

In your answer, you've found a particular solution, but not the general one. $18, 53, 88,...$etc. all solve the system. Your question stated that you only need to find one value, in which case your solution is fine. But if you need a complete solution set, this answer may be helpful. Of course, once you've found a single solution, you don't have to go through this process. CRT guarantees the uniqueness of the solution modulo the product of the other two moduli, i.e. $\pmod{35}$ in this case. So if you've already found $53$ to be a solution you know that every solution will be equivalent to this modulo $35$.

So $x \equiv 53 \pmod{35} \implies x \equiv 18 \pmod {35}$ since $53 - 35 = 18$. This way you can immediately generalise your particular solution.

Answer 2

I reckon I've worked it out, so I'll just answer my own question.

Firstly, make sure the GCD of your mods are equal to one. ie in this example:

 gcd(5,7) = 1

Then solve the question in 2 parts since there are 2 simultaneous equations.

x = _______ + ________

where the first underlined bit is for mod5 and the second part is for mod7

Then, you add a 7 to the first section of your solution, as 7(mod7) is 0 and will cancel that section out. You do the same for the second section but with a 5, as 5(mod5) is also 0. (sorry I'm not very good at explaining.)

so you get:

 x = 7 * ______ + 5 * _______

working with the first section, you get:

 7 = (2 mod 5) but we need it in terms of (3 mod 5)

so by inspection, we find that: 7*4=28 which is (3 mod 5) we can now update the solution to

 x = 7*4 + 5* _____

Doing the same thing again to the second section of the solution, we get:

 x = 7*4 + 5*5 = 53

Answer 3

If you are still looking for a way to find solutions to your problem, you might want to consider this.

The “method” is based on introducing parameter variables so that the original variables can be expressed as parameter variables. If such an expression exist, then enumerating integer values for the parameter variables would then yield integer solutions to the original variables. The “method” might work for any arbitrary linear system of equations where the domain of each variable is from the set of Integers.

I hope you find this useful. – john

A solution to your problem using the "method":

Answer 4

Given x ≡ a (mod m) and x ≡ b (mod n), if there is a solution at all, there are infinitely many of them, all congruent modulo lcm(m,n).

(If m and n are coprime, a solution must exist per the Chinese Remainder Theorem; if they're not coprime, a solution only exists if a ≡ b mod gcd(m,n)).

The first step is to find any solution to Bézout's Identity: a pair of integer values u and v such that um+vn = gcd(m,n). In this case, you're looking for solutions to 5u + 7v = 1.

In general you can get solutions to this sort of problem using an extension of Newton's method, but for small values like this it's not hard to find some by inspection. The first one that occurs to me is u=3, v=-2, since 5(3)+7(-2) = 15-14 = 1.

Any valid solution for u and v will give you one of the infinitely-many solutions to the original problem when you plug them into the expression (bum + avn)/gcd(m,n). That is, multiply each remainder by the other divisor and its Bézout coefficient, add the products together, and divide by the GCD of the moduli (which is 1 in this case).

For your problem that expands to 4(3)5 + 3(-2)7 = 60 - 42 = 18. And sure enough, 18 ≡ 5 (mod 3) and 7 (mod 4).

Another solution I can see for u and v is u=-4 v=3, since 7(3)+5(-4) = 21 - 20 = 1; that yields 4(-4)5 + 3(3)7 = -80 + 63 = -17, which is of course congruent to 18 modulo lcm(5,7) = 35.