# using (mod)

• Jun 30th 2008, 06:09 AM
glost
using (mod)
The sum of digits of the number 8215 is 8 + 2 +1 +5 = 7 (mod 9)
Observe also 8215 = 9 9912) + 7= 7 (mod 9) does this hold for any number? Explain

Suppose we want to compute the product 8215 x 3567 modulo 9. Replacing these numbers by those obtained by adding their digits and reducting modulo 9 gives 16 x 21 = 7 x 3 =21 = 3 (mod 9). Is it true that 8215 x 3567 = 3 (mod 9)? Explain
• Jun 30th 2008, 09:46 AM
Moo
Hello,

Quote:

Originally Posted by glost
The sum of digits of the number 8215 is 8 + 2 +1 +5 = 7 (mod 9)
Observe also 8215 = 9*912 + 7= 7 (mod 9) does this hold for any number? Explain

We know that for any positive integer a, $\displaystyle 9$ divides $\displaystyle 10^a-1$ (geometric sum)
Therefore :

$\displaystyle 10^a-1 \equiv 0 (\bmod 9)$

--> $\displaystyle \boxed{10^a \equiv 1 (\bmod 9)}$

---------------------
Goin' back to the problem :

$\displaystyle 8215=8\times \underbrace{10^3}_{\equiv 1}+2\times \underbrace{10^2}_{\equiv 1}+1\times \underbrace{10^1}_{\equiv 1}+5\times \underbrace{10^0}_{\equiv 1} \equiv \underbrace{8\times 1+2\times 1+1\times 1+5\times 1}_{8+2+1+5} (\bmod 9)$

Note that this is the sum of the digits of the number.

$\displaystyle 8215 \equiv 16 (\bmod 9) \equiv \boxed{7} (\bmod 9)$

This holds for any number (try it out with a,b,c,d,... as the digits, you will see the same conclusion)

Quote:

Suppose we want to compute the product 8215 x 3567 modulo 9. Replacing these numbers by those obtained by adding their digits and reducting modulo 9 gives 16 x 21 = 7 x 3 =21 = 3 (mod 9). Is it true that 8215 x 3567 = 3 (mod 9)? Explain
This uses basic rules of modular arithmetic (and the previous question) :

$\displaystyle a \equiv c (\bmod n) \implies ab \equiv bc (\bmod n)$