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?