Homework Help: Congruence sum proof

1. Feb 9, 2009

dancergirlie

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. Feb 9, 2009

Hitman2-2

Let anan-1...a0 represent your number, where the ai are the digits. Another way of representing your number is $$10^n a_n + \cdots + 10^0 a_0$$. So what you want to prove is that 9 divides $$(10^n a_n + \cdots + 10^0 a_0) - (a_n + \cdots + a_0)$$

Last edited by a moderator: Feb 9, 2009
3. Feb 9, 2009

dancergirlie

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?

4. Feb 9, 2009

Hitman2-2

Every term in $$a_n (10^n - 1) + a_{n-1} (10^{n-1} - 1) + \cdots + a_1 (10-1)$$ is of the form $$a_i (10^i -1)$$. If you can prove that 9 divides any such term, then you are done.

Can you figure out how to prove that 9 divides $$a_i (10^i -1)$$ for all positive integers i?

5. Feb 9, 2009

dancergirlie

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

6. Feb 9, 2009

Dick

10 is congruent to 1 mod 9. Hence 10^n is congruent to 1 mod 9.

7. Feb 10, 2009

dancergirlie

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?

8. Feb 10, 2009

dancergirlie

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

9. Feb 10, 2009

dancergirlie

well (10^n -1) that is

10. Feb 10, 2009

Dick

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.