1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Congruence sum proof

  1. Feb 9, 2009 #1
    1. The problem statement, all variables and given/known data

    Prove that every positive integer is congruent to the sum of its digits (mod 9). (for example 38 is congruent to 11(mod 9))

    2. Relevant equations

    If a is congruent to b (mod n), then n divides (a-b)

    3. The attempt at a solution

    let a= {a1, a2..... a9} be digits
    where 0 is less than or equal to a which is less than 10

    That is where i don't know where to go, i have these digits and I don't know how to show that when added together they = b(mod 9)
    maybe i should do something about 9 divides some digits, but i have no clue.

    Any suggestions or tips would be great =)
  2. jcsd
  3. Feb 9, 2009 #2
    Let anan-1...a0 represent your number, where the ai are the digits. Another way of representing your number is [tex] 10^n a_n + \cdots + 10^0 a_0 [/tex]. So what you want to prove is that 9 divides [tex] (10^n a_n + \cdots + 10^0 a_0) - (a_n + \cdots + a_0) [/tex]
    Last edited by a moderator: Feb 9, 2009
  4. Feb 9, 2009 #3
    I know this may sound stupid, but how am I supposed to show that. Right now I have:

    9 divides a_n (10^(n)-1 )+ a_(n-1) (10^(n-1)-1)+⋯a_1 (10-1).
    How do i get that 9 divides that?
  5. Feb 9, 2009 #4
    Every term in [tex] a_n (10^n - 1) + a_{n-1} (10^{n-1} - 1) + \cdots + a_1 (10-1) [/tex] is of the form [tex] a_i (10^i -1) [/tex]. If you can prove that 9 divides any such term, then you are done.

    Can you figure out how to prove that 9 divides [tex] a_i (10^i -1) [/tex] for all positive integers i?
  6. Feb 9, 2009 #5
    well a_1(10-1)= a_1(9), and 9 divides a_1(9). So does that mean that it divides all i? I thought that only would apply for n=1
  7. Feb 9, 2009 #6


    User Avatar
    Science Advisor
    Homework Helper

    10 is congruent to 1 mod 9. Hence 10^n is congruent to 1 mod 9.
  8. Feb 10, 2009 #7
    Where does the a_n go? wouldn't (a_1)10 be congruent to 1 mod 9, meaning that a_n would be congruent to 1 mod 9?
  9. Feb 10, 2009 #8
    ok, nevermind, i just figured out that that doesn't matter because 9 divides both a_n10^n and also 9 divides just 10^n
  10. Feb 10, 2009 #9
    well (10^n -1) that is
  11. Feb 10, 2009 #10


    User Avatar
    Science Advisor
    Homework Helper

    a_n doesn't have to be congruent to anything. The point is that (10^n-1) is divisible by nine, as HitMan-2 pointed out. So a_n*10^n is congruent to a_n mod 9.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook