# 92 arithmetic/tests.for.divisibility/three.p

## Description

This article is from the Puzzles FAQ,
by Chris Cole chris@questrel.questrel.com and Matthew Daly
mwdaly@pobox.com with numerous contributions by others.

# 92 arithmetic/tests.for.divisibility/three.p

What is the test to see if a number is divisible by three?

arithmetic/tests.for.divisibility/three.s

A number is divisible by three iff the sum of its digits is divisible by three.

First, prove 10^N = 1 mod 3 for all integers N >= 0.

1 = 1 mod 3. 10 = 1 mod 3. 10^N = 10^(N-1) * 10 = 10^(N-1) mod 3.

QED by induction.

Now let D[0] be the units digit of N, D[1] the tens digit, etc.

Now N = Summation From k=0 to k=inf of D[k]*10^k.

Therefore N mod 3 = Summation from k=0 to k=inf of D[k] mod 3. QED

Continue to: