# 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

### cookiemonster

This might help:

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

cookiemonster

7. Mar 16, 2004

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

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?