Product of two natural numbers
YAP Von Bing
March 9, 2022
Let \(a\) and \( b \) be natural numbers, i.e., 1, 2, 3, etc. Let their product be \( n = ab \) . You might agree that \( n \) cannot be smaller than \( a \) or \( b \) , i.e., \( a \le n \) and \( b \le n \) . This is easy enough to see in numerous examples. \( 2 \times 3 = 6 \) , and 6 is greater than both 2 and 3. \( 1 \times 5 = 5 \) , and both 1 and 5 are less than or equal to the product 5. The second example shows that generally the inequality is not strict, i.e., we do not always have \( a < n \) . How can we demonstrate the general fact, or \( {\bf theorem} \) ? How can we prove that for any natural numbers \( a \) and \( b \) with product \( n = ab \) , both \( a \le n \) and \( b \le n \) hold? We cannot check every case, because there are infinitely many natural numbers.
Here is a visual approach. \( n \) identical squares can be arranged in a rectangle with \( a \) rows, each having \( b \) squares. Clearly, the total \( n \) cannot be less than the number of squares in a column, \( a \) , or the number of squares in a row, \( b \) . We may translate the pictorial argument into algebra.
\( n = ab = a + a(b-1) \ge a \)
The second equality is key, which reflects the separation of a column from the others. Since \( b-1 \ge 0 \) , \( a(b-1) \ge 0 \) , hence we are certain that \( n \ge a \) . Both the picture and the algebra also show that in the special case \( b > 1 \) , indeed \( n > a \) . You might want to make a similar argument for \( n \ge b \) .
Let us suppose that \( a \le b \) . Can you say something stronger than \( a \le n \) ? For instance, can you find an expression $f(n)$ in terms of \( n \) , such that \( a \le f(n) \le n \) ? You might get a clue from concrete examples:
\( 16 = 1 \times 16 = 2 \times 8 = 4 \times 4, \)
\( 24 = 1 \times 24 = 2 \times 12 = 3 \times 8 = 4 \times 6 \)
or the special case \( a=b \) , where \( a = \sqrt{n} \) .
It makes sense to try \( f(n) = \sqrt{n} \) . Our examples work:
\( 1, 2, 4 \le 4 = \sqrt{16} \)
\( 1, 2, 3, 4 \le 4.9 \approx \sqrt{24} \)
Hence we are more confident of the \( {\bf conjecture}: \ \)
Let \( a \le b \) be any natural numbers. Let \( n = ab \) . Then \( a \le \sqrt{n} \) .
We now give a proof of the conjecture. Suppose the first two sentences hold but the conclusion is false, i.e., \( a > \sqrt{n} \) . Combining it with the first sentence gives \( b \ge a > \sqrt{n} \) . Multiplying the two inequalities, we get \( ab > n \) , which violates the second sentence. Assuming the conclusion is false has led to an absurdity. Therefore, the assumption is wrong, and the conclusion indeed follows. This concludes the proof. Now that the conjecture has been proved, it becomes a theorem.
The above is an example of \( {\bf proof by contradiction} \) , which was used by the ancient Greeks to prove a variety of facts about numbers, such as there are infinitely many prime numbers, and the more surprising fact that \( \sqrt{2} \) is irrational, i.e., it cannot be expressed as the ratio of two natural numbers. The proofs of these facts are more intricate, but the underlying sturcture is exactly the same as here. In order to show that a conclusion follows from a premise, we assume that the conclusion is false. Then we combine the premise with the assumption logically to derive a false statement. Something has gone wrong. Since the derivation is logically correct, we must give the assumption up. Hence the conclusion must follow from the premise.
As practice, you may want to write down a proof by contradiction to show that with the same premise as above, \( b \ge \sqrt{n} \) . This fact also follows directly from the previous fact. From \( a \le \sqrt{n} \) , we know \( 1/a \ge 1/\sqrt{n} \) . Hence
\( b = n \times \frac{1}{a} \ge n \times \frac{1}{\sqrt{n}} = \sqrt{n} \)
We saw earlier that if \( a=b \) , then both inequalities become equalities. Furthermore, if \( a<b \) , then both inequalities are strict. In conclusion, we may make a more complete statement as follows:
\( {\bf Theorem.} \) Let \( a \le b \) be any natural numbers, and let \( n = ab \) . Then
\( a \le \sqrt{n} \le b \)
Moreover, if \( a<b \) , then \( a < \sqrt{n} < b \) . Otherwise, \( a=b = \sqrt{n} \) .
Notice that the conjecture and theorem are general statements, i.e., they are about all possible values of \( a \) and \( b \) , as long as the values are natural numbers. The phrase “any natural numbers” should serve as a reminder of the generality. You may want to formulate analogous conjectures about three natural numbers \( a, b, c \) and their product \( abc \) , given \( a \le b \le c \) , and then try to prove or disprove them.