[Math] Solving systems of basic congruences

discrete mathematicsmodular arithmetic

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!

Best Answer

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$