Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

3 Answers 3

up vote 1 down vote accepted

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?

share|improve this answer
    
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

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 $

share|improve this answer

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}$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.