Testing Divisibility by 3.

So I did go ahead and program a dynamically generated Sieve of Eratosthenes, but I just wanted to write a quick post about divisibility by 3 before I write a novel about the Sieve.

Many of us know the trick for checking an integer’s divisibility by 3: just sum the digits and if the resulting sum is divisible by 3, then our original integer is as well.  (Note–an integer is a whole number. 4 is an integer; 4.1 is not. 58403695 is an integer; 1/2 is not.)

But why does it work?

Well, it has to do with the fact that we are on a base 10 number system–that is, all integers can be expressed as the sum of multiples of powers of 10. 10 to the zero power is 1.  (Any number raised to the zero power is 1.) 10 to the 1 power is 10.  So the integer 6 can be expressed as 6 * 100, and the integer 50 as 5 * 101.  How about 72? That’s 7 * 10 + 2 * 1, or 7 * 101 + 2 * 100.  So if we can break an integer apart like this, we can manipulate the expression algebraically to check divisibility by 3.

Lets take 72 again, which is (7 * 10) + (2 * 1).  We can rewrite it as 7 * (9 + 1) + (2 * 1).

The first parentheses, when expanded, give us (7 * 9) + (7 * 1) = 63 + 7 = 70, as expected.

Let’s rewrite this expression as (7 * 9) + 7 + 2. We know 7 * 9 is divisible by 3, because 3 * 3 = 9.

So that leaves us only with our remaining 2 digits to sum and check. 2 + 7 = 9, which is definitely divisible by 3.  So 72 is divisible by 3.

Let’s look at a larger integer whose even divisibility by 3 we could not determine from sight.

Take, for example, the integer 169431.

We can rewrite it in the form:

(1 * 105) + (6 * 104) + (9 * 103) + (4 * 102) + (3 * 101) + (1 * 100)

= 1( 99999 + 1 ) + 6( 9999 + 1 ) + 9( 999 + 1 ) + 4( 99 + 1) + 3( 9 + 1) + 1

= 1(99999) + 6(9999) + 9(999) + 4(99) + 3(9) + (1 + 6 + 9 + 4 + 3 + 1)

All multiples of 99999, 9999, 999, 99, and 9 are divisible by 3, so that leaves us only with the digits we factored out. Summing (1 + 6 + 9 + 4 + 3 + 1) gives us 24, which is divisible by 3.

Thus the integer 169431 is divisible by 3.

Of course this can be generalized for any integer n.

Given n, where n is in the set of positive real numbers, n can be expressed as
a * (10k -1 + 1) + b * (10k-1 – 1 + 1) +… + x * (100), where a, b, x are positive real numbers.
By algebraic manipulation, this can be rewritten as
a * (10k -1) + b * (10k-1 – 1) +…+ a + b +…+ x.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s