Abstract Algebra - Numbers Divisible by 9 (Technical Proof)

This is a technical proof of how if you sum the didgets of any number and that sum is divisble by 9, then the original number is divisible by 9.

Let ai denote a digit in mod 10 and let a1a2…an denote a positive integer with an n number of digits. Then, 9a1a2…an Î Z+ if and only if 9Si = 1, n ai Î Z+.

Proof. Factoring out a 10n from the nth digit gives

a1a2…an – 1an
= 10(n – 1)a1 + 10(n – 2)a2 + … + 10(n – (n – 1))an – 1 + 10(n – n)an
= 10(n – 1)a1 + 10(n – 2) + … + 10an – 1 + an

Since [(10n – 1) + 1] = 10n,

= [(10n – 1 – 1) + 1]a1 + [(10n – 2 – 1) + 1]a2 + … + [(10 – 1) + 1]an – 1 + an.

Distributing ai to each term gives

= (10n – 1 – 1)a1 + a1 + (10n – 1 – 1)a2 + a2 + … + (10 – 1)an – 1 + an – 1 + an

Because 9(10n – 1) "n Î Z+, 9 can be factored out from each (10n – 1) to leave (S i = 0, n 10i).

= 9a1(S i = 0, n – 1 10i) + 9a2(S i = 0, n – 2 10i) + … + 9an – 1 + a1 + a2 + … + an (5)

The number a1a2…an – 1an contains the sum Si = 1, n ai. Let 9Si = 1, n ai = R. Factoring out 9 from each term gives

a1a2…an – 1an = 9a1(S i = 0, n – 1 10i) + 9a2(S i = 0, n – 2 10i) + … + 9an – 1 + 9R
= 9[a1(S i = 0, n – 1 10i) + a2(S i = 0, n – 2 10i) + … + an – 1 + R]

Because a1a2…an – 1an can factor out 9, 9a1a2…an – 1an. This could not have occurred if R did not factor out nine as well. Further, if 9a1a2…an – 1an, then a1a2…an – 1an gives a 9R term by equation (6). 9R = Si = 1, n ai and 9Si = 1, n ai. QED