Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How do you show

  1. Mar 14, 2004 #1
    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. jcsd
  3. Mar 15, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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 [tex] x_nx_{n-1}\ldots x_0[/tex] it stands for

    [tex] 10^nx_n+10^{n-1}x_{n-1}+\ldots +x_0[/tex]

    What do you know about modulo arithmetic?
  4. Mar 15, 2004 #3
    I cant use modulo arithmetic to solve this.
  5. Mar 15, 2004 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  6. Mar 15, 2004 #5
    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.
  7. Mar 15, 2004 #6
    This might help:

    [tex]10^nx_n \equiv x_n\textrm{ mod }3[/tex]

  8. Mar 16, 2004 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook