# How does divisibility test using congruence work?

In the book, it said:

Let $n = a_{k}10^{k} + a_{k-1}10^{k-1} + a_{k-2}10^{k-2} + ... + a_110 + a_0$
Then, because $10 \equiv 0 \pmod{2}$ it follows that $10^j \equiv 0 \pmod{2^j}$

What congruence property did they use in this case? Is that:
If $a \equiv b \pmod{k_1}$ and $c \equiv d \pmod{k_2}$ then, $ab \equiv cd \pmod{k_1k_2}$ ?

I saw one property in the book, which is:
$a \equiv b \pmod{k}$ and $c \equiv d \pmod{k}$then, $ab \equiv cd \pmod{k}$ But I really don't understand how this property relates to the one above it. Any idea?

-
To typeset moduli for congruences, use \pmod{k}. For example, $a\equiv b \pmod{c}$ produces $a\equiv b \pmod{c}$. –  Arturo Magidin Feb 26 '11 at 4:00

Maybe it will help to notice that $10^j=2^j5^j$, so clearly $2^j|10^j$, and thus $10^j\equiv 0\pmod{2^j}$.

Essentially for that particular case, you have $10\equiv 0\pmod{2}$, which says $2|10$. It follows that $10^j\equiv 0\pmod{2^j}$ because $10^j$ has $j$ factors of $10$, each of which is divisible by $2$, and thus you can divide by $j$ factors of $2$. That is $2^j|10^j$, or $10^j\equiv 0\pmod{2^j}$.

Does that make it more clear?

-
Thanks, it's clear now ;) However, is there a property like If $a \equiv b ( mod \ \ k_1 )$ and $c \equiv d ( mod \ \ k_2 )$ then, $ab \equiv cd ( mod \ \ k_1k_2 )$ ? –  Chan Feb 26 '11 at 2:04
@Chan, I'm afraid there isn't such a property. For a counterexample, notice $5\equiv 2\pmod{3}$ and $7\equiv 2\pmod{5}$. However, $10\not\equiv 14\pmod{15}$. By the way, \pmod{k_1} will typeset to $\pmod{k_1}$, not $(mod\ k_1)$ if you prefer the mod text to not be italicized. –  yunone Feb 26 '11 at 2:12
hehe what a similar example! –  milcak Feb 26 '11 at 2:13
@milcak, ah I just saw your comment on your answer! How coincidental. –  yunone Feb 26 '11 at 2:19
Thanks for your clear explanation. –  Chan Feb 26 '11 at 2:35

You you need to use this property $j$ times, since:

$10 \equiv 0 \mod{2}$ and $10 \equiv 0 \mod{2}$, then $10 \cdot 10 \equiv 10^2 \equiv 0 \mod{2^2}$

You know that $2|10$ so it must be that $2^2 | 10^2$ (factorization). Repeat again:

$10 \equiv 0 \mod{2}$ and $10^2 \equiv 0 \mod{2^2}$, then $10 \cdot 10^2 \equiv 10^3 \equiv 0 \mod{2^3}$

So in the end you get:

$10 \equiv 0 \mod{2}$ and $10^{j-1} \equiv 0 \mod{2^{j-1}}$, then $10 \cdot 10^{j-1} \equiv 10^j \equiv 0 \mod{2^j}$

-
So the the 2 inside the mod part can be multiplied? –  Chan Feb 26 '11 at 2:06
@Chan Here yes (the reason why is contained in yunone's answer). But in general you cannot always do this: consider $7 \equiv 2 \mod{5}$ and $2 \equiv 2 \mod{3}$, but $7\cdot 2 \equiv 14 \equiv -1 \mod{15}$ but $2\cdot 2 \equiv 4 \mod{15}$. –  milcak Feb 26 '11 at 2:12
how did you guys come up with exactly the same example! Amazing ^_^! –  Chan Feb 26 '11 at 2:36

It's no coincidence that the congruence sign $\equiv$ resembles the equality sign $=\:$. This notation was explicitly devised to help remind you of the fact that congruence relations share many of the same properties as the equality relation. In particular, just like equations in the ring of integers, ring congruences can be added, multiplied, scaled, etc. Thus, considering this analogy, how would you prove that $\rm\ n = 0\ \Rightarrow\ n^{\:j} = 0\$ for $\rm\:n\:$ an integer? Precisely the same proof works for congruences.

For completeness, here is a proof of the congruence product rule

LEMMA $\rm\ \ A\equiv a,\ B\equiv b\ \Rightarrow\ AB\equiv ab\ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A-a,\:\:\ B-b\ \Rightarrow\ m\ |\ (A-a)\ B + a\ (B-b)\ =\ AB - ab$

-