Welcome to our community

Be a part of something great, join today!

Number Theory System of congruences, not relatively prime moduli

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,829
Hello!!! (Wave)

I want to solve the following system of congruences:

$$x \equiv 13 \pmod{40} \\ x\equiv 5 \pmod{44} \\ x \equiv 38 \pmod{275}.$$


I have thought the following:

$$x \equiv 13 \pmod{40} \Leftrightarrow x \equiv 13 \pmod{2^3 \cdot 5}$$

$$x \equiv 5 \pmod{44} \Leftrightarrow x \equiv 5 \pmod{2^2 \cdot 11}$$

$$x \equiv 38 \pmod{275} \Leftrightarrow x \equiv 38 \pmod{5^2 \cdot 11}$$


$$x \equiv 13 \pmod{2^3 \cdot 5} \Leftrightarrow x \equiv 13 \pmod{2^3} \text{ and } x \equiv 13 \pmod{5} \ \ (1)$$

$$x \equiv 5 \pmod{2^2 \cdot 11} \Leftrightarrow x \equiv 5 \pmod{2^2} \text{ and } x \equiv 5 \pmod{11} \ \ (2)$$

$$x \equiv 38 \pmod{5^2 \cdot 11} \Leftrightarrow x \equiv 38 \mod{5^2} \text{ and } x \equiv 38 \pmod{11} \ \ (3)$$

$(1)$: $x \equiv 5 \pmod{2^3}$ and $x \equiv 3 \pmod{5}$

$(2)$: $x \equiv 1 \pmod{2^2}$ and $x \equiv 5 \pmod{11}$

$(3)$: $x \equiv 13 \pmod{5^2}$ and $x \equiv 5 \pmod{11}$


Am I right so far?

How can we continue? Can we somehow apply the Chinese Remainder Theorem? (Thinking)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,265
Hey evinda !!

Unfortunately we cannot apply CRT directly since the modulo numbers are not co-prime.

We can solve the problem however, by working through the equations as follows:

$x\equiv 13 \pmod{40}\Rightarrow x=13+40k \tag 1$
$x \equiv 5 \pmod{44} \Rightarrow 13+40k \equiv 5 \pmod{44} \Rightarrow 40k \equiv -8 \pmod{44} \tag 2$

Normally we can solve (2) directly by multiplying with the inverse of $40$ with respect to $44$, but in this case this inverse doesn't exist because $40$ and $44$ are not co-prime.
So instead we make an intermediate step, and then get the inverse:
$$40k = -8 + 44\ell \Rightarrow 10k=-2+11\ell \Rightarrow 10k\equiv -2 \pmod{11} \\ \Rightarrow k \equiv [10]^{-1}_{11} \cdot -2 \pmod{11} \Rightarrow k= [10]^{-1}_{11}\cdot -2 + 11m$$
where $[10]^{-1}_{11}$ is the inverse of $10$ modulo $11$.

Can we find $k$ now? And substitute it back into (1)?
Afterwards, we can repeat with the last equation. (Thinking)
 

Olinguito

Well-known member
Apr 22, 2018
251
Some time ago, I made an observation on the S.O.S. forum on what happens with simultaneous congruence equations when the modulo numbers are not coprime: Chinese remainder theorem.

Let’s take the first two equations: $x\equiv13\pmod{40}\equiv5\pmod{44}$. A solution exists if and only if $13\equiv4\pmod d$ where $d=\gcd(40,44)=4$. This holds, and so a solution exists. Noting that $x=93$ satisfies the congruences and $\mathrm{lcm}(40,44)=440$, the general solution of the congruence is $x=93+440k$, $k\in\mathbb Z$.

Now we do the same for the congruences $x\equiv93\pmod{440}\equiv38\pmod{275}$. First check that a solution exists: $\gcd(440,275)=55$, $93\equiv38\pmod{55}$. It does. Then find $l=\mathrm{lcm}(440,275)$, find a particular solution $x_0$ to the congruences, and the general solution will be of the form $x=x_0+lk$, $k\in\mathbb Z$.

$x=1413+2200k$, $k\in\mathbb Z$.