How do I solve simultaneous congruence modulo equations

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}$$

• Goggle the "Chinese Remainder Theorem". – coffeemath Nov 27 '14 at 0:15
• There are two approaches the general (Chinese Remainder Theorem and the associated algorithms) and the particular, which is well-suited to small moduli like the $5$ and $7$ of your problem. – André Nicolas Nov 27 '14 at 0:16

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.

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