modular arithmetic

Question

an integer n is divisible by 3 if and only if the sum of digits of n is divisible by 3. In other words, if n= a₀+ 10 a₁ +10² a₂ +…+ 10^k a_k, then n is divisible by 3 if and only if a₀+a₁+a₂+…+a_k is divisible by 3. Example: 12765312 is divisible by 3 because 1+2+7+6+5+3+1+2=27 is divisible by 3; indeed, 12765312 / 3 = 4255104.

Answer 1

Question: an integer n is divisible by 3 if and only if the sum of digits of n is divisible by 3. In other words, if n= a0+ 10 a1 +102 a2 +…+ 10k ak, then n is divisible by 3 if and only if a0+a1+a2+…+ak is divisible by 3.

Proof

lemma1

10^p - 1 = 9*10^(p-1) + 9*10^(p-2) + ... + 9*10 + 9

10^p - 1 = 3k

Hence, 3 | 10^p - 1  (3 divides 10^p - 1)

Let N = a0 + 10.a1 +10^2. a2 +…+ 10^n.an

and M = a0 + a1 + a2 +…+ an

If 3 | M, then M = 3q, say.

N - M = (a0 + 10.a1 +10^2. a2 +…+ 10^n.an) - (a0 + a1 + a2 +…+ an)

N - M = a1(10 - 1) + a2(10^2 - 1) + ... + an(10^n - 1)

Using lemma1,

N - M = a1.3k1 + a2.3k2 + ... + an.3kn = 3m, say.

N - 3q = 3m

N = 3s  => 3 | N

Q.E.D.