# Thread: Show that 3 divides n if and only if 3 divides (am+am-1+...+a2+a1+a0).

1. ## Show that 3 divides n if and only if 3 divides (am+am-1+...+a2+a1+a0).

let n be contained in natural numbers and n=amam-1...a2a1a0 where each ai is a digit of n. Show that 3 divides n if and only if 3 divides (am+am-1+...+a2+a1+a0). Hint: write n as a base 10 expression in terms of sum of its digits and use number 4.

This is a homework problem for my discrete math class but it is not graded so we are allowed to work with others on it.

I do not even know where to start so could someone help me I do not understand at all.

2. Originally Posted by marielange
let n be contained in natural numbers and n=amam-1...a2a1a0 where each ai is a digit of n. Show that 3 divides n if and only if 3 divides (am+am-1+...+a2+a1+a0). Hint: write n as a base 10 expression in terms of sum of its digits and use number 4.

This is a homework problem for my discrete math class but it is not graded so we are allowed to work with others on it.

I do not even know where to start so could someone help me I do not understand at all.
Hint: $\displaystyle n = a_n10^n + a_{n - 1}10^{n - 1} +_{\dots} + 10a^1 + a^0$

What is 10 mod 3? So what is 10^k mod 3 for any k?

-Dan

3. you can look at it this way. if n is just one digit long, then of course, 3 has to divide n.

now, suppose n is two digits long, let's say n = ab, that is n = 10a + b. suppose 3 divides a + b.

that means a+b = 3k. we can write this as: a = 3k - b. so then n becomes 10(3k - b) + b = 30k - 10b + b = 30k - 9b = 3(10k - 3b).

on the other hand, if 3 divides 10a + b, so that 10a + b = 3m, then a + b = 10a + b - 9a = 3m - 9a = 3(m - 3a).

let's look at 3-digits strings: n = abc = 100a + 10b + c. then if 3 divides a + b + c, a = 3k - b - c.

so n = 100(3k - b - c) + 10b + c = 300k - 90b - 99c = 3(100k - 30b - 33c). if we have 100a + 10b + c = 3m,

then a + b + c = 100a + 10b + c - 90a - 9b = 3m - 90a - 9b = 3(m - 30a - 3b). do you see the pattern?

the difference between an10^n + a(n-1)10^(n-1) +...+ 10a1 + a0 and an + a(n-1) +...+ a1 + a0 is always going to be a multiple of 3.

this tells us that n and the sum of its digits are the same number modulo 3.

in fact, you can sharpen this even further. the difference is always going to be a multiple of 9, so the exact same logic tells us

that n is divisible by 9 if and only if the sum of its digits is divisible by 9.