# System of congruences, not relatively prime moduli

• MHB
• evinda
In summary, the problem is to find a solution for the system of congruences: $$x \equiv 13 \pmod{40} \\ x\equiv 5 \pmod{44} \\ x \equiv 38 \pmod{275}.$$ After simplifying and breaking down the congruences, we can see that we cannot apply the Chinese Remainder Theorem directly. However, we can find a solution by working through the equations and finding the general solution for each pair of congruences. The final solution will be in the form of $x=x_0+lk$, where $x_0$ is a particular solution and $k$ is an integer.
evinda
Gold Member
MHB
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)

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)

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

## 1. What is a system of congruences?

A system of congruences is a set of equations in the form of x ≡ a (mod m), where x is a variable, a is a constant, and m is the modulus. This system is used to find solutions for x that satisfy all of the equations.

## 2. What does it mean for moduli to be relatively prime?

Two moduli are relatively prime if they have no common factors other than 1. This means that they do not share any common divisors, and therefore, any number that is a solution for one modulus will also be a solution for the other modulus.

## 3. How is a system of congruences with non-relatively prime moduli solved?

A system of congruences with non-relatively prime moduli can be solved using the Chinese Remainder Theorem. This theorem states that if the moduli are pairwise coprime (meaning they do not share any common factors with each other), then there will be a unique solution for x that satisfies all of the congruences.

## 4. Can a system of congruences have more than one solution?

Yes, a system of congruences can have multiple solutions. This is especially true for systems with non-relatively prime moduli, as there may be multiple numbers that satisfy the congruences for each modulus.

## 5. How is a system of congruences used in mathematics?

Systems of congruences are used in various areas of mathematics, such as number theory, algebra, and cryptography. They are particularly useful in solving problems involving modular arithmetic, which has applications in computer science, engineering, and other fields.

• General Math
Replies
4
Views
1K
• General Math
Replies
1
Views
2K
• Precalculus Mathematics Homework Help
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
1K
• Precalculus Mathematics Homework Help
Replies
1
Views
1K
• Precalculus Mathematics Homework Help
Replies
7
Views
2K
• Precalculus Mathematics Homework Help
Replies
3
Views
2K
• Precalculus Mathematics Homework Help
Replies
6
Views
850
• Precalculus Mathematics Homework Help
Replies
3
Views
1K
• Precalculus Mathematics Homework Help
Replies
7
Views
1K