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.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.