A simple proof I don't get

[psi20]

I have little background in number theory, groups, conditions, and stuff like that. So I got a book called Teach Yourself Mathematical Groups and this is one of the examples.

 

Prove that a necessary and sufficient condition for a number N expressed in denary notation to be divisible by 3 is that the sum of the digits of N is divisible by 3.

 

I see the proof in the book, but I can't get it. It shows what denary notation is, decimal notation written out like 1x10^4 + 2x10^3 ...

 

Let N= a 10^n + b 10^(n-1) + ... + z (The book uses subscripts instead of different letters for the digits a, b, ..., z)

The proof says: If 3 divides N, then 3 divides a 10^n + b 10^(n-1) + ... + z .

The part I don't understand is 'For all powers of 10, dividing by 3 gives a remainder of 1. So the remainder when N is divided by 3 is a + b + ... z.'

How did that work?

[phyti]

10^k=(9+1)^k

expand this into 9^k+...+1^k

all the terms are divisible by 3 except the last

hope that helps

[psi20]

Ah yeah, now it makes sense, thanks.