Proving t(n) Divisible by 3 Implies n is Divisible by 3

[Ed Quanta]

That iff the sum of the digits of n is divisible by 3, then n is divisible by 3.

Defining t(n) to be the sum of the digits of n, can I just use induction show n-t(n)=3x is true. Since we know if this statement is true, then it can't be true for n+1, do I use n+3 as what I am trying to show holds true by induction?

 

[matt grime]

Whenever you have a question asking you about digits in the number, you've got to think that it might have something to do with expansion.

So, if the number looks like x_nx_{n-1}\ldots x_0 it stands for

10^nx_n+10^{n-1}x_{n-1}+\ldots +x_0

What do you know about modulo arithmetic?

 

[Ed Quanta]

I can't use modulo arithmetic to solve this.

 

[matt grime]

Why on Earth not? (that's sort of rhetorical)

If you must use induction, then you can.Induction, despite being taught in terms of n and n +1, only requires the idea of successors, they could be labelled obviously by n and n+1, but there's no reason why they can't be 0,3,6,...,n+3,n+6...

You should probably find out about the strong principle of induction, too.

 

[Ed Quanta]

Yeah, I learned the strong principle of induction but I still don't really see why it works or rather when it is necessary opposed to showing n implies n+1. Yeah, I know there is a way not involving induction which is probably prettier. Out of curiosity though, how would you use modular arithmetic to do this. You don't have to write it out, just throw a couple of ideas. We learned modular arithmetic after this problem was assigned which is why I don't want to use that in my proof.

 

[cookiemonster]

This might help:

10^nx_n \equiv x_n\textrm{ mod }3

cookiemonster

 

[matt grime]

For the inductive proof: suppose we want to show n is divisible by 3, well, that is true iff n-3 is divisible by three. The result follows by induction (you'll need base cases for n=0,1,2 to be sure) if you can show that if the result holds for n-3, then it holds for n.This is easy if n-3 ends in 0,1..6, for then the sum of the digits in n is the sum of the digits of n-3 plus 3, and then the sum of n's digits is divisible by 3 iff n is follows by induction. If n-3 ends in 7,8, or 9 you'll have to think a little harder.