# CNT - Modulo

• Nov 8th 2007, 01:14 PM
AgentNXP
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'
• Nov 8th 2007, 10:31 PM
AgentNXP
• Nov 8th 2007, 11:13 PM
angel.white
Quote:

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
• Nov 8th 2007, 11:53 PM
angel.white
Quote:

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}$
• Nov 9th 2007, 07:30 AM
topsquark
Quote:

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
• Nov 10th 2007, 12:13 AM
angel.white
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)
• Nov 10th 2007, 12:30 AM
DivideBy0