System of congruences, not relatively prime moduli

[evinda]

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)

 

[I like Serena]

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]

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

Spoiler

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