Originally Posted by

**CaptainBlack** First a base case:

If a and b are two numbers less than 1 both divisible by 3 then their sum

is divisible by 3, since they are both zero.

Now suppose that for some k>1 that for all pairs of integers

(a,b; 3|a, 3|b, a<=k, b<=k)

implies that 3|(a+b)

Now consider a pair of (u,v;3|u, 3|v, u<=k+1, v<=k+1),

then if u<=k and v<=k; 3|(u+v) by supposition.

If k<u<=k+1, v<=k, then u=u'+3, u'<k, and so 3|(u'+v) which implies 3|(u+v)

If u<=k, k<v<=k+1, then v=v'+3, v'<k, and so 3|(u+v') which implies 3|(u+v)

If k<u<=k+1, k<v<=k+1, then u=u'+3, u'<k, and v=v'+3, v'<k, and so 3|(u'+v') which implies 3|(u+v)

So if for some k>1 that for all pairs of integers (a,b; 3|a, 3|b, a<=k, b<=k) implies that 3|(a+b), then for all pairs of integers (a,b; 3|a, 3|b, a<=k+1, b<=k+1) implies that 3|(a+b). Which with the base case proves by induction

that:

If a and b are two numbers both divisible by 3 then their sum

is divisible by 3

This could probably be made neater by taking n=3 for the base case, and steping from

k to k+3 in the inductive step.

RonL