Fact about divisibilty by 3

(1) The positive integer n is divisible by 3 ⇔ the sum of digits of the positive integer n is divisible by 3.

Proof:

Let n = d₁ + d₂10¹ + ... + d_m10^m-1 where m is number of digits of number n,
and d₁ , d₂ , ... , d_m are its digits.
Let S(q) is sum of digits of natural number q,
and let n+3 = d^'₁ + d^'₂10¹ + ... + d^'_m^'10^{m^'-1} where m^' is number of digits of number n+3,
and d^'₁ , d^'₂ , ... , d^'_m^' are its digits.

In the case where adding 3 to n changes d₁ only - we obtain: d^'₁ = d₁+3, d^'₂ = d₂, ... , d^'_m^' = d_m, m^'=m
so S(n+3) = S(n) + 3
thus
(2) S(n+3) - S(n) = 3
Otherwise - there is arithmetic overflow(s) - let's say up to position k, and obviously 2≤k≤m^'.
If k=2 then must be: m^'=m, d^'₁=d₁-7, d^'₂=d₂+1, d^'₃=d₃, ... , d^'_m^' = d_m
so S(n+3) = S(n) - 7 + 1 = S(n) - 3⋅2
thus
(3) |S(n+3) - S(n)| = 3⋅2
If m^'≥k>2 then must be: m≤m^'≤m+1, d₁≥7, d₂=d₃= ... =d_k-1=9, d_k<9 (*)
and
d^'₁=d₁-7, d^'₂=d^'₃= ... =d^'_k-1=0, d^'_k=d_k+1 (*)
so S(n+3) = S(n) -7 - 9(k-2) + 1 = S(n) - 3(3(k-2)+2) = S(n) - 3(3k-4)
thus
(4) |S(n+3) - S(n)| = 3(3k-4)
(*) If m^'=m+1 then d_m+1 does not exist but without any problems we can assume that d_m+1=0.

Equations (2), (3) and (4) implicate that S(n) and S(n+3) have identical rests by division by 3.
Of course S(1)=1, S(2)=2 and S(3)=3 thus in based on Principle of Mathematical Induction
the equipotency (1) is true.

♦

Analogically it is possible to prove similar fact about divisibility by 9. Of course, I finally learned (and admire) Gauss's proof, beautifully simple in its simplicity – very intuitive even with a minimal introduction to the world of number theory. Interested readers can easily find it online.

Fact about divisibilty by 3

∗∗∗