Prime or Not: Determining Primes Through Square Root

A prime number is a integer greater than that is divisible only by 1 and itself. A number that is not prime is composite.

To determine whether a number is prime or not, we have to divide it by all numbers between 1 and itself . For example, to say that 257 is prime, we must be sure that it is not divisible by any number between 1 and 257. In this discussion, the word “numbers” refer to positive integers.

Are you prime or not?

Dividing a number by all numbers between 1 and itself is burdensome especially for large numbers. In this post, we discuss a shorter way of determining if a number is prime and explain why the method works.

Before proceeding with primes, let us examine the behavior of the factors (or divisors) of composite numbers.  Instead of finding the divisors, we pair the numbers as factors, where the first factor is increasing and the product of each pair is equal to the number. For instance, we have the pairs (1,12), (2,6), and so on as factors of 12 as shown in the first table.

Notice that the 4th, 5th, and 6th pairs are just “reverses” of the first three pairs. In effect, we just need to include the first three pairs to be sure that we have all the factors.  This is also the similar in the second example. We only need to test the divisibility up to 4 and we have already all the factors. No need to test divisibility by 5 up to 16.  (To verify further, try factors of other composite numbers.)

You have probably noticed that there is some sort of “middle number” in both tables denoted by the red-colored text. After the middle number, the pairs are mere repetitions of the other pairs.

In the first table, the middle number is 3, while in the second table, the middle number is 4. Four is the square root of 16, and testing more perfect squares (the reader is encouraged to do so) will confirm the observation.

From above, we can conjecture that every composite number has a factor less than or equal to its square root.  Proving this is the same as proving that a number that has no divisor greater than 1 and less than its square root is prime.

The Formal Proof

Conjecture: Every composite number has a proper factor less than or equal to its square root.

Proof: We use proof by contradiction.  Suppose n is composite. Then, we can write n = ab, where a and b are both between 1 and n.  If both a > \sqrt{n} and b> \sqrt{n}, then (a)(b) > (\sqrt{n})(\sqrt{n}) which means that ab > n. This contradicts our assumption that ab = n. Hence, at least one of a, b is less than or equal to \sqrt{n}. That is, if n is composite,  , then n has a prime factor p \le \sqrt{n}.

Leave a Reply