### How to Find out if a Number is Prime

YAP Von Bing
May 3, 2022

A natural number $$n > 1$$ is $${\bf prime}$$ if its only factors are 1 and itself, or equivalently, $$n$$ is $${\bf divisible}$$ by 1 and itself only. Clearly, 2 and 3 are prime. 4 is not prime, or $${\bf composite}$$, since $$4 = 2 \times 2$$. 5 and 7 are the only other primes less than 10. Imagine representing $$n$$ identical squares as a rectangle. For example, 6 squares can be put in a rectangle with height 1 and width 6, and also one with height 2 and width 3. How many ways can 12 be represented as a tall rectangle, i.e., one with width $$w$$ and height $$h$$ satisfying $$w \le h$$? State a criterion on whether $$n$$ is prime in terms of the rectangular representation. Check that it works on a few cases, then prove that it works in general.

Here is one way to state the criterion:

A natural number $$n > 1$$ is prime if the only way to represent it as a tall rectangle of squares is the one with $$w=1$$ and $$h=n$$.

Given a natural number $$n > 1$$, how can we find out if it is prime? Starting with the rectangle of width 1 and height $$n$$, increase the width to $$w$$ and decrease the height to $$h$$, while keeping $$wh=n$$ and $$w \le h$$. As the rectangle gets wider and shorter, if we find one where both $$w$$ and $$h$$ are natural numbers, then $$n$$ is composite. For instance, let $$n$$ be even. The rectangle with $$w=2$$ and $$h=n/2$$ works, provided $$2 \le n/2$$, or $$n \ge 4$$. Therefore any even number greater than 2 is not a prime. By our criterion, $$n$$ is prime if we cannot find any natural numbers $$w$$ and $$h$$ such that $$wh=n$$ and $$w \le h$$, except for $$w=1$$ and $$h=n$$. Notice that we can now apply the theorem from the post The Product of Two Natural Numbers with $$a=w$$ and $$b=h$$, to derive the following plan.

To find out if $$n>2$$ is prime, try dividing it by a natural number $$w$$, where $$2 \le w \le \sqrt{n}$$. If no such $$w$$ divides $$n$$ exactly, then $$n$$ is prime.

For example, $$\sqrt{101} = 10.05$$ to two decimals. To find out if 101 is prime, we just need to check if it can be divided by $$2, 3, 4, \ldots, 10$$. But we can reduce the work further. If $$n$$ is divisible by 4, then it must be divisible by 2. If $$n$$ is divisible by 6, then it must be divisible by 2 and also by 3. Can you find a more efficient way for checking if a number is prime along this line, and state it like the above?