# How do you show

1. Mar 14, 2004

### 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 cant be true for n+1, do I use n+3 as what I am trying to show holds true by induction?

2. Mar 15, 2004

### 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?

3. Mar 15, 2004

### Ed Quanta

I cant use modulo arithmetic to solve this.

4. Mar 15, 2004

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

5. Mar 15, 2004

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

6. Mar 15, 2004

This might help:

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