Doug’s World

Is a number prime?

How can you tell if a big number is prime? The number 23,571,113,171,923, say: is that prime? Where do you start?

Sure, you could write a program to check every integer up to the square root of your number, and if none of those divide evenly into it then you have a prime. But suppose you wanted to figure this kind of thing out without a computer? (Really, people used to do stuff like this.)

10 and its close cousins 2 and 5

I’ll bet if the number above ended in 0, most folks would intuitively know it isn’t prime. Ending in 0 is a sure-fire clue that the number is probably divisible by 10, don’t you think? (Assuming base-10 notation, of course.)

And if the number ends in 2, 4, 6, or 8, most folks would intuitively know that it’s even, divisible by 2, and therefore not prime.

When you’re checking whether a number is divisible by two, did you ever think about why you only need to check the last digit? One way to look at it is that you only need to check the last digit because that’s how much greater your number is than a known multiple of 10, and 10 is divisible by 2. That same sort of thinking applies to determining whether a number is divisible by greater powers of 2. It works like this:

To check if a number is divisible by 2, you only need to check whether the last 1 digits are divisible by 2, because 10 is divisible by 2.

To check if a number is divisible by 4, you only need to check whether the last 2 digits are divisible by 4, because 100 is divisible by 4.

To check if a number is divisible by 8, you only need to check whether the last 3 digits are divisible by 8, because 1000 is divisible by 8.

To check if a number is divisible by 16, you only need to check whether the last 4 digits are divisible by 16, because 10000 is divisible by 16.

And for identical reasons, since 10 is 2 times 5, this sort of thinking works for checking whether a number is divisible by powers of 5:

Check the last 1 digits for divisibility by 5 (because 10 is divisible by 5)
Check the last 2 digits for divisibility by 25 (because 100 is divisible by 25)
Check the last 3 digits for divisibility by 125 (because 1000 is divisible by 125)
Check the last 4 digits for divisibility by 625 (because 10000 is divisible by 625)

Well, that’s just dandy. But what about checking for divisibility by numbers that aren’t factors of 10, the base of our numbering system?

Divisible by 3 or 9?

Many people know this one: to determine whether a number is divisible by 3, add up the digits in the number. If the result is divisible by 3, then the original number is divisible by 3 too. You can use this as a quick way to show that the number mentioned above is not divisible by 3.

Note that you can also add up the digits of the result of the calculation, to determine whether it is divisible by 3, and continue collapsing your number until it gets down to something that’s obviously divisible by 3 or not. So in our example above, the digits of 23,571,113,171,923 add up to 46, whose digits add up to 10, whose digits add up to 1, which is not divisible by 3, so neither is the original number.

Divisibility by 9 works the same way: if the digits add up to a number that’s divisible by 9, then — and only then — the original number was also divisible by 9.

As it says in all those math books, “proof of this assertion will be left as an exercise for the reader.”

Divisible by 7?

This is a personal favorite of mine: remove the last digit, double it, and subtract that from the remaining number. This manipulation preserves the 7-divisibility of the original number. (Proving this one is even more fun than the 3s/9s rule.)

For example, is 142857 divisible by 7?

Take off the 7, double it to 14, subtract that from 14285: the result is 14271
Take off the 1, double it to 2, subtract that from 1427: result is 1425
Take off the 5, double it to 10, subtract that from 142: result is 132
Take off the 2, double it to 4, subtract that from 13: result is 5

And 5 isn’t divisible by 7, so neither is 142857.

Divisible by 11?

For Divisibility by 11, you take the first digit, subtract the 2nd digit, add the 3rd digit, and so on, all the way to the end of the number. The result of this process will be exactly as “divisible by 11″ as your original number. Specifically, the result has the same remainder when divided by 11 as your original number has when divided by 11. (Proving this one is a bit simpler than the case for 7 above.)

Is 121 divisible by 11? Yes, because 1-2+1=0, the remainder when 121 is divided by 11. Is 142857 divisible by 11? Yes, because 1-4+2-8+5-7=-11, the “remainder” when 142857 is divided by 11. (If the remainder is divisible by 11, so is the original number. Prove that, Pythagoras.)

Divisible by larger primes?

There are many more of these types of tricks for larger primes factors, but they grow increasingly complex as the factors get larger. Well, some are simple, such as the rule for 19, which is like the rule for 7 except you add the doubled digit instead of subtracting it. I used to know these up through 29, but don’t use them much any more and can’t remember 13, 17, 23 and 29. Here’s a page with the rules for testing divisibility by all the primes less than 50.

“On the factorization of large numbers”

The French mathematician Marin Mersenne made an assertion in 1644 whose validity was still being openly debated over 200 years later. I’m not going to bother to explain it (check out Mersenne.org if you’re really interested) except to say that it involves predicting whether numbers of the form 2 to the N minus 1 are prime.

As of 1903, it was still unknown whether M67 (Mersenne number 67), which is 2 raised to the 67th power less one, was a prime. If it was proved to not be prime, then Mersenne’s conjecture would be disproven. The problem is, Mersenne’s numbers grew very rapidly, and it could take a person months to do the longhand arithmetic involved in searching for divisors of large numbers. M67, for example, is over 20 digits long.

So when mathematician F. N. Cole demonstrated that M67 was not a prime in 1903, it was an impressive achievement. And there’s a great story of how Cole announced his finding, which was written up by Eric Temple Bell in his essay “The Queen of Mathematics.” I’ve quoted Bell’s description below, from my copy in James R. Newman’s 4-volume hardcover book series “The World of Mathematics,” published by Simon & Schuster in 1956. (My Dad had these books in the living room, and so do I. They’re great stuff if you like math stories, and they’ve been re-issued in a Dover paperback edition.)

Anyway, here is Bell’s description of Cole’s feat from Newman’s book:

I should like here to preserve a small bit of history before all the American mathematicians of the first half of the twentieth century are gone. When I asked Cole in 1911 how long it had taken him to crack M67 he said “three years of Sundays.” But this, though interesting, is not the history. At the October, 1903, meeting in New York of the American Mathematical Society, Cole had a paper on the program with the modest title On the factorization of large numbers. When the chairman called on him for his paper, Cole — who was always a man of very few words — walked to the board and, saying nothing, proceeded to chalk up the arithmetic for raising 2 to the sixty-seventh power. Then he carefully subtracted 1. Without a word, he moved over to a clear space on the board and multiplied out, by longhand,

193,707,721 x 761,838,257,287

The two calculations agreed.

Mersenne’s conjecture — if such it was — vanished into the limbo of mathematical mythology. For the first and only time on record, an audience of the American Mathematical Society vigorously applauded the author of a paper delivered before it. Cole took his seat without having uttered a word. Nobody asked him a question.

Man, if that story doesn’t give you goosebumps, what does?

This entry was posted on Thursday, August 24th, 2006 at 11:38 pm. You can subscribe to comments on this post through its RSS feed.