In my last blog post on solving the Impossible
Puzzle, I promised that I would prove the following.

For any positive integer N, there exists only one pair of positive
integers a and b such that 1 < a < b and ab = N if and only if N
is a product of two different primes, a cube of a prime, or a fourth
power of a prime.

In the last post, I gave an intuitive demonstration of why this should
be true. However, intuition may be misleading and should not be relied
upon. We need to prove this by pure logic.

From the fundamental
theorem of arithmetic, we know that any integer greater than 1 can
be expressed as a unique product of primes. A corollary of this theorem
is:

Any positive integer N > 1 can be written uniquely in a canonical form N
=
p_{1}^{k1}p_{2}^{k2}
… p_{n}^{kn} where, each k_{i}
is a positive integer and each p_{i} is a prime for positive
integers i, 1 ≤ i ≤ n.

From this, let me prove the following lemma.

Lemma: The number of possible factors of N
is (k_{1} + 1)(k_{2} + 1)…(k_{n} + 1)

Proof: Any factor of N can be expressed as
p_{1}^{r1}p_{2}^{r2}
… p_{n}^{rn}, where 0 ≤
r_{i} ≤ k_{i} for 1 ≤ i ≤ n.

In the expression for the factor of N, we can see that each
p_{i} can be raised by any power between 0 and k_{i}
(including 0 and k_{i}). So, there are k_{i} + 1
different ways to choose the exponent for each p_{i} in the
above expression.

Hence, the total number of possible factors is: (k_{1} +
1)(k_{2} + 1)…(k_{n} + 1). ∎

Now, let me prove the theorem I mentioned in the beginning of this post.

Theorem: For any positive integer N, there
exists only one pair of positive integers a and b such that 1 < a
< b and ab = N if and only if N is a product of two different primes,
a cube of a prime, or a fourth power of a prime.

Proof: The sufficiency of the condition is
easy to show.

If N is a product of two different primes, p_{1} and
p_{2}, where p_{1} < p_{2}, the set of
factors of N is {1, p_{1}, p_{2}, N}. Thus, it has only
two factors a = p_{1} and b = p_{2} such that 1 < a
< b and ab = N.

If N is a cube of a prime p, N = p^{3} and the set of factors of
N is {1, p, p^{2}, p^{3}}. a = p and b = p^{2}
are the only factors such that 1 < a < b and ab = N.

If N is a fourth power of a prime p, N = p^{4} and the set of
factors of N is {1, p, p^{2}, p^{3}, p^{4}}. a =
p and b = p^{3} are the only factors such that 1 < a < b
and ab = N.

Now, let us prove the necessity of the condition.

If a positive integer N has only one two factors a and b such that 1
< a < b, it implies that there are two possibilities of the total
set of factors of N. If N is not a perfect square, the total set of
factors of N is {1, a, b, N} where 1 × N = a × b. If N is a
perfect square, such that √N = r, the total set of factors of N is
{1, a, r, b, N} where 1 × N = a × b = r × r.

So, in any case, the total number of factors N has, is either 4 or 5.

Let us write N as
p_{1}^{k1}p_{2}^{k2}…p_{n}^{kn}
for primes p_{1}, p_{2}, &hellip, p_{n} and
positive integers k_{1}, k_{2}, …, k_{n}.

For n ≥ 3, the total number of factors N has, is (k_{1} +
1)(k_{2} + 1)…(k_{n} + 1) ≥ (k_{1} +
1)(k_{2} + 1)(k_{3} + 1) ≥ 6. But we have shown that
the total number of factors of N is either 4 or 5. So, n must be less
than 3. Hence, we can write N as
p_{1}^{k1}p_{2}^{k2}
and thus the total number of factors it has can be written as
(k_{1} + 1)(k_{2} + 1). Without loss of generality, let
us assume k_{1} ≤ k_{2}.

All possible factorings of 4 and 5 are as follows.

- 4 = 1 × 4 = (0 + 1)(3 + 1)
- 4 = 2 × 2 = (1 +
1)(1 + 1)
- 5 = 1 × 5 = (0 + 1)(4 + 1)

From the
above enumeration of factorings we can see that one of the following
must be true.

- k
_{1} = 0 and k_{2} = 3 - k
_{1} =
k_{2} = 1 - k
_{1} = 0 and k_{2} =
4

If k

_{1} = 0 and k

_{2} = 3, N =
p

_{2}^{3}.

If k_{1} = k_{2} = 1, N = p_{1}p_{2}.

If k_{1} = 0 and k_{2} = 4, N =
p_{2}^{4}.

So, we have shown that N is a product of two primes, a cube of a prime,
or a fourth power of a prime.∎

For a few more interesting results on factors, see http://susam.in/downloads/mathematics/theorems/factors.pdf.