Determining whether a number is prime (or “The Benefits of Square-Rooting a Number, Part I”)

Something that comes up now and again in various contexts during lessons is how to tell whether a number is prime. My usual advice has been to use divisibility rules*, and if none work, then it’s likely that the tested number is prime. Likely is not the same thing as certain, however, and, as the numbers get bigger, the divisibility rules will tend to be less and less helpful. For example, it’s easy to rule out that 51 is a composite number, i.e. not prime (and not ‘1’), but what about 1591? None of the common divisibility rules work, but that doesn’t mean 1591 is necessarily prime.

rialto_gondoliers
Ponte di Rialto over the Canal Grande, Venice, Italy. Completed in 1591. Photo of bridge by Saffron Blaze, http://www.mackenzie.co.

Knowing that there had to be some better way to determine whether a number is prime, I did a web search and found the following method:

To determine whether a number n is prime, square-root the number and let the result be r. Next, try to divide n by all the prime numbers that are less than r.

Let’s see how this method works with a composite and a prime number, 539 and 113 respectively.
01_n539

02_n113

Okay, but why square-root? Why would square-rooting reduce the possible prime factors of a number? Shouldn’t we test all the primes less than the number?

To understand the motivation behind square-rooting, let’s look at a perfect square such as 144 and what whole numbers we can multiply to get it. Keep in mind that the square root of 144 is 12.

03_list144

What do we notice? Well, the line 12×12 separates the above list into two groups that mirror each other. That is, all the factors of 144 in the first group are in the second group (e.g. 9×16 is the same as 16×9). So, if we’re looking to list all the factors of 144, we would only be repeating ourselves if we looked beyond 12×12.

This is why we square-root a number and look at the possible factors below the number’s root. And since it would be redundant to test with the composite factors, we only test with prime ones. For 144, out of 2, 3, 4, 6, 8 and 9, it would only be necessary to try 2 or 3, to show that 144 is composite.

And so what about 1591? We’ll use the same process as above, but, to speed things up, we’ll also eliminate any primes we know won’t work using our divisibility rules for 10 or fewer.

04_n1591
*Rules that allow you to see whether a given whole number is divisible by 2, 3, 4 etc. For example, 411 is divisible by 3 because the sum of 4,1 and 1 equals 6, a number divisible by 3. I tend only to do tests for numbers that can be divided by 10 or fewer. Look at Math is Fun for more details on divisibility rules: www.mathsisfun.com/divisibility-rules.html
† There are other ways to test whether a number is prime, but this way stuck out for me because it seemed easy to carry out. Check Wikipedia for other methods. The method described in this post is called trial division.
‡ Any composite number can be written as a product of primes. This is known as the prime factorization of a number. Check out Math is Fun (again) to find out more about prime factorization. If it’s unclear why prime factorization matters here, think of the number 30. You know that 6 divides 30, but you also know that 2 divides 6. Thus, 30 is divisible by 2, a prime factor. So, if you’re looking to see whether 30 is prime, just stick to 30’s prime factors to avoid dividing by its composite factors unnecessarily!

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