# Math Help - numbertheory

1. ## numbertheory

hi can anyone help me with this problem in number theory with regards to prime number? i don't know how to proive this..can someone help?

Prove that an integer is divisible by 3 if and only if the sum of its digits is divbisble by 3. Prove that an integer is divisible by 9 if and only if the sum of its digits is divisible by 9...thanls

2. Let $N=[a_na_{n-1}...a_1a_0]_{10}$. Then $N=10^na_n+10^{n-1}a_{n-1}+...10a_1+a_0$. Notice that $10 \equiv 1 \pmod 9$ so $10^n \equiv 1 \pmod 9$ and $N=10^na_n+10^{n-1}+...10a_1+a_0 \equiv a_n+a_{n-1}+...+a_1+a_0 \pmod 9$. That is, $9 \mid N$ iff $9 \mid a_n+a_{n-1}+...+a_1+a_0$

If you aren't familiar with congruences, notice that:
$N=10^na_n+10^{n-1}a_{n-1}+...10a_1+a_0$ $= \left ((10^n-1)a_n+(10^{n-1}-1)a_{n-1}+..+9a_1 \right)+\left (a_n+a_{n-1}+...+a_1+a_0 \right )$

For divisibility by 3, notice that $10 \equiv 1 \pmod 3$ and argue in the same way as in the case with divisibility by 9.

3. Originally Posted by DavidEriksson
Let $N=[a_na_{n-1}...a_1a_0]_{10}$. Then $N=10^na_n+10^{n-1}a_{n-1}+...10a_1+a_0$. Notice that $10 \equiv 1 \pmod 9$ so $10^n \equiv 1 \pmod 9$ and $N=10^na_n+10^{n-1}+...10a_1+a_0 \equiv a_n+a_{n-1}+...+a_1+a_0 \pmod 9$. That is, $9 \mid N$ iff $9 \mid a_n+a_{n-1}+...+a_1+a_0$

If you aren't familiar with congruences, notice that:
$N=10^na_n+10^{n-1}a_{n-1}+...10a_1+a_0$ $= \left ((10^n-1)a_n+10^{n-1}a_{n-1}+..+9a_1 \right)+\left (a_n+a_{n-1}+...+a_1+a_0 \right )$

For divisibility by 3, notice that $10 \equiv 1 \pmod 3$ and argue in the same way as in the case with divisibility by 9.

thank you very much for the reply..Dave...really thanks