# Math Help - CNT - Modulo

1. ## CNT - Modulo

where '=' means 'congruent to'

Solve both system of equations:

1.
x = 0 (mod 2)
x = 0 (mod 3)
x = 1 (mod 5)
x = 6 (mod 7)

Answer: x = ? (mod 210)

2.
x = 0 (mod 4)
x = 1 (mod 9)
x = 2 (mod 25)
x = 3 (mod 49)

Answer: x = ? (mod 44100)

where '=' means 'congruent to'

3. Originally Posted by AgentNXP
Just glancing at the first one, 6/2=0, 6/3=0, 6/5=1 remainder 1, 6/7 =0 remainder 6

4. Originally Posted by SnipedYou
Hmm is this true?

$a \equiv b \pmod{m}$
$a \equiv c \pmod{n}$
$a \equiv b + c \pmod{m \cdot n}$?
No,

For example a=5, b=9, c=12, m=4, n=7

$5 \equiv 9 \pmod{4} \Rightarrow \mbox{True}$
$5 \equiv 12 \pmod{7} \Rightarrow \mbox{True}$
$5 \equiv 21 \pmod{28} \Rightarrow \mbox{False}$

5. Originally Posted by AgentNXP
1.
x = 0 (mod 2)
x = 0 (mod 3)
x = 1 (mod 5)
x = 6 (mod 7)

Answer: x = ? (mod 210)
See here.

2, 3, 5, and 7 are pairwise coprime, so we may apply the Chinese Remainder theorem.

To start the answer, as you mentioned, will be a modulo 2 x 3 x 5 x 7 = 210.

We need to find a set of pairs of integers $(r_i, s_i)$ such that
$2r_1 + \left ( \frac{210}{2} \right )s_1 = 1$

$3r_2 + \left ( \frac{210}{3} \right )s_2 = 1$

$5r_3 + \left ( \frac{210}{5} \right )s_3 = 1$

$7r_4 + \left ( \frac{210}{7} \right )s_4 = 1$

As example solutions I get
$(r_1, s_1) = -51, 1)$
$(r_2, s_2) = -23, 1)$
$(r_3, s_3) = -25, 3)$
$(r_4, s_4) = -17, 4)$
(Any solutions to these equations is acceptable.)

So the solution to the system of equivalences is
$x = 0 \cdot \left ( \frac{210}{2} \right )s_1 + 0 \cdot \left ( \frac{210}{3} \right )s_2 + 1 \cdot \left ( \frac{210}{5} \right )s_3 + 6 \cdot \left ( \frac{210}{7} \right )s_4$

$x \equiv 846 \bmod 210 = 6 \bmod 210$

You do the second one.

-Dan

6. I got 14752

Thanks for post, topsquark, it was much easier to follow your example than my book's.

I just wish I understood why this worked so that I wouldn't forget it again (it might be on my final, I'm taking discrete math right now)