1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Easy number theory problem

  1. Feb 18, 2014 #1
    An integer is divisible by 9 if and only if the sum of its digits is divisible by 9

    Proof by induction?
     
  2. jcsd
  3. Feb 18, 2014 #2
    I am new to proofs never done them, I am stuck ac=b 9c=b ex. 9c=81 so c is an int. thus divisible let b= d+dn so 9c=d+dn then 9c=d+dn+dn+9
     
  4. Feb 19, 2014 #3

    hilbert2

    User Avatar
    Science Advisor
    Gold Member

    In the decimal system, an integer with ##n## digits is written in the form
    ##\sum_{k=0}^{n-1}a_{k}10^{k}##, where the numbers ##a_{k}## are the digits.

    Now consider the number
    ##\sum_{k=0}^{n-1}a_{k}10^{k}-\sum_{k=0}^{n-1}a_{k}##,
    and deduce that it must always be divisible by 9. Then use the fact that if a sum of two integers, ##m+n## is divisible by 9 then either both ##m## and ##n## are divisible by 9 or neither of them is. That way you can prove the theorem.
     
  5. Feb 19, 2014 #4

    Curious3141

    User Avatar
    Homework Helper

    Have you worked with modulo notation? Easiest way is to reduce the decimal representation ##\sum_{k=0}^{n-1}a_{k}10^{k} \pmod{9}## where the digits ##0 \leq a_k \leq 9## and make the observation that ##10 \equiv 1 \pmod{9}##. The rest should quickly follow, but if you get stuck, post back.
     
  6. Feb 19, 2014 #5
    This is a great hint. Using this method, you can actually prove a stronger statement:

    ## a \equiv (\sum a_k) \ (\text{mod } 9) ##

    where ##a_k## are the digits of ##a##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Easy number theory problem
  1. Number theory problem (Replies: 1)

  2. Number theory problem (Replies: 2)

Loading...