1
$\begingroup$

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?

  • 0
    To typeset moduli for congruences, use `\pmod{k}`. For example, `$a\equiv b \pmod{c}$` produces $a\equiv b \pmod{c}$.2011-02-26

3 Answers 3

1

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

  • 0
    how did you guys come up with exactly the same example! Amazing ^_^!2011-02-26
2

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 $

1

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?

  • 0
    Thanks for your clear explanation.2011-02-26