Proof: If the sum of the digits of a number is divisible by 3 then the number is divisible by 3

Given a number with digits of the form

  [pmath] X_N …X_4 X_3 X_2 X_1 X_0 [/pmath]

If the sum of these digits is equal to a number that is divisible by 3 then the number is divisible by 3.  Proof follows

Starting with    [pmath] X_1 X_0 [/pmath]  with  [pmath] X_0 [/pmath] which must be 0.3,6,9 then  

  [pmath] X_1 + X_0 [/pmath] is said to be divisible by 3 thus  [pmath] X_1 + X_0 = 3n_1[/pmath]   Where [pmath] n_1[/pmath] is an integer

  [pmath] 10X_1 + X_0 [/pmath]     should be divisible by 3.

  Rearranging the terms of 

      [pmath] X_1 + X_0 = 3n_1[/pmath] 

Yields

     [pmath] X_1 = 3n_1 – X_0 [/pmath] 

Substituting in 

    [pmath] 10X_1 + X_0 [/pmath]  

Yields

    [pmath] 10( 3n_1 – X_0 ) + X_0 [/pmath]  

Simplifying yields

   [pmath]  30n_1 – 9X_0  [/pmath]  

And therefore it is a sufficient condition that if [pmath] X_1 + X_0 [/pmath] be divisible by 3 then    [pmath] X_1 X_0 [/pmath] is divisible by 3 and by extension   [pmath] X_N …X_4 X_3 X_2 X_1 X_0 [/pmath] is divisible by 3 if   [pmath] X_N+ …+X_4+ X_3+ X_2+ X_1+ X_0  [/pmath] is divisible by 3.

As you might guess the same applies to all powers of 3 with 9 being the most useful next integer.