Take the 2-minute tour ×

I'm having some difficulty with a problem and I was hoping I could find some help here.

We've been covering congruences in my Discrete Math class, and, while I understand what they mean, I can't seem to solve systems of congruences greater than 2 equations in size.

What I mean is, I can solve problems that look like this:

$x \equiv 4 \mod 5$

$x \equiv 7 \mod 8$

I understand that I can solve this by doing something along the lines of:

$x = 5k + 4$

$5k + 4 \equiv 7 \mod 8$

$5k \equiv 3 \mod 8$

$k = 7$

$x = 5*7 + 4$

therefore $x = 39$

But I can't seem to figure out how to expand this to three (or more) equations, like so:

$x \equiv 4 \mod 5$

$x \equiv 7 \mod 8$

$x \equiv 3 \mod 6$

Disclaimer: I made these numbers up and I'm assuming there's always an answer. If this system doesn't work, any example problem will do. I'm just confused about the process.

Thank you!

share|improve this question
en.wikipedia.org/wiki/Chinese_remainder_theorem –  user17762 Nov 28 '12 at 20:19
See this post, e.g., also this post –  amWhy Nov 28 '12 at 20:25
Thank you both! –  Benjamin Kovach Nov 28 '12 at 20:30

2 Answers 2

up vote 2 down vote accepted

To construct an $x$ equal to $x_1 \mod m_1$, $x_2 \mod m_1$ and $x_3 \mod m_3$.

we would like some expression $x = A + B + C$ such that mod $m_1$ kills $B$ and $C$, mod $m_2$ kills $A$ and $C$ etc.. and gives the correct values ($x_1$, $x_2$, ..)

For the things to get killed in the right we we should have $x = m_2 m_3 A' + m_1 m_3 B' + m_1 m_2 C'$ so e.g. reduction mod $m_1$ gives $m_2 m_3 A'$ so we should set $A' = x_1 \cdot \text{inverse of (}m_2 m_3\text{) mod }m_1$ and similarly with the other two.

share|improve this answer
I've been trying to solve this with the Chinese Remainder Theorem as stated in the comments above, and it looks like it's unsolvable. Is that true? Could you (or anyone) check it? –  Benjamin Kovach Nov 28 '12 at 20:39
Thank you. Yeah, I just noticed that the moduli must be coprime. I think I understand the process now, though. Thanks! –  Benjamin Kovach Nov 28 '12 at 20:43

The system

$x \equiv 4 \mod 5$

$x \equiv 7 \mod 8$

$x \equiv 3 \mod 6$

should be prepared more before solving.

The reason for this is that two of the modulus share a common factor: 8 and 6 are both multiples of 2.

This could lead to a clash where the two different equations demand contradictory properties mod 2, in this case it's actually fine though:the mod 2 part of both these equations agree so we should cast the 2 part out of one of the equations (this loses no information)

$x \equiv 4 \mod 5$

$x \equiv 7 \mod 8$

$x \equiv 3 \mod 3$

share|improve this answer

Your Answer


