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 * 10^{0}, and the integer 50 as 5 * 10^{1. }How about 72? That’s 7 * 10 + 2 * 1, or 7 * 10^{1} + 2 * 10^{0}. 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 * 10^{5}) + (6 * 10^{4}) + (9 * 10^{3}) + (4 * 10^{2}) + (3 * 10^{1}) + (1 * 10^{0})

= 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 * (10^{k} -1 + 1) + b * (10^{k-1} – 1 + 1) +… + x * (10^{0}), where a, b, x are positive real numbers.

By algebraic manipulation, this can be rewritten as

a * (10^{k} -1) + b * (10^{k-1} – 1) +…+ a + b +…+ x.

### Like this:

Like Loading...

## Published by E. E. Esterly

Hi! I'm Elizabeth, and I like to program robot brains, write software, think about and play around with numbers, and hang out with my awesome husband (also a programmer) and my dog (most certainly not a programmer). I'm a graduate student in Computer Science department at the University of New Mexico.
I came to Computer Science and Robotics from a non-traditional background. I'm a first-generation college student with a BFA in Fine Art and minors in French and Japanese. After receiving my art degree, I traveled the world with my husband tattooing for a few years before becoming increasingly interested in robotics and Computer Science...and the rest is history!
View all posts by E. E. Esterly