Proving Congruence Sum: Positive Integer Mod 9

[dancergirlie]

Homework Statement

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

Homework Equations

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

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 =)

 

[Hitman2-2]

Let a_na_n-1...a₀ represent your number, where the a_i 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)

 

[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?

 

[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?

 

[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

 

[Dick]

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

 

[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?

 

[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

 

[dancergirlie]

well (10^n -1) that is

 

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