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.
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.