2002 IMO Shortlist Problems/N3
Problem
Let be distinct primes greater than 3. Show that
has at least
divisors.
Solutions
Solution 1
Lemma 1. If , then
has at least twice as many divisors as
.
Proof. For every divisor of
,
is clearly a divisor of
, but not
.
Lemma 2. If and
are relatively prime odd numbers, then the greatest common factor of
and
is 3.
Proof. Clearly, 3 divides both and
. Now, suppose that there is some
which divides both
and
. Then
. But this means that both
and
are divisible by half the order of 2 in mod
, contradicting our assumption that
and
are relatively prime.
We now note that since
,
we know that is divisible by
, and, by symmetry,
also, and therefore also by
.
We now prove the result by induction on . Our base case,
, is easy, since we know that
is divisible by 3, and is greater than 27. Now, set
and
. By Lemma 2, we know that
and
are relatively prime; hence
has at least
factors, by the inductive hypothesis.
We know that divides
. We also know that
, whence
. Then by Lemma 1,
.
Q.E.D.
Solution 2
We proceed by induction. For our base case, , we note that
is divisible by 3. Since
,
is clearly greater than 3 and cannot be a larger power of three, since this would require
. Therefore
has some other prime factor and therefore at least 4 factors overall.
Now, suppose the proposition holds for . Without loss of generality, let
be the minimum of
. We shall abbreviate
. We note the relation
.
Since has at least
factors, it will suffice to show that
is relatively prime to
, and has at least four factors.
We note that in general, has remainder
when divided by
. But
cannot divide
, as this would require
when
is relatively prime to
. Hence
and
are relatively prime.
We now claim that has at least four factors. We start by noting that in general,
divides
, since the roots of the former are the nonreal
th roots of unity and
.
Since clearly , it is sufficient to show that the former is not the square of the latter (i.e., that the former is either a higher power of the latter, or some other prime divides the latter, either of which implies that the former has at least four factors). But this follows from
Thus has at least four factors and is relatively prime to
, completing the induction.
Solution 3
We proceed by induction. Base case . Observe that
, and since
,
so
has at least 4 divisors.
Now suppose the proposition holds for .
lemma 1:
if with
and
both being odd, then
.
Proof:
let p be a prime that divides both and
. Then p divides both
and
. Since
(mod
) and
(mod
),
divides
and
. But,
, so
. Hence proven.
lemma 2:
, with
being a prime greater than
.
Proof;
It suffices to show that . for
, the only solution to
(mod
) is
.
is the smallest natural
such that
(mod
). This means that if
(mod
),
(mod
), but
is a prime greater than
, so this is not possible.
Note that . Let
. Note that
. So
. Note that
.
I will now prove . Note that
. We wish to prove
. Rearrange the inequality to get
. Note that
, which implies the inequality. Since
,
.
Also, note that . This means
has at least four factors. Note that if
,
would be relatively prime to
, which would mean
has at least
factors.
Assume and
are not relatively prime. Then there exists some prime
such that
. Let
,
and
, with
being the prime in question. Note that
. (
is relatively prime to
). Then
. Let
be the number of divisors of
. Then
. Note that
, so
. From the inductive step
, so
. This implies
, which completes the induction.
QED