1991 IMO Problems/Problem 2
Problem
Let be an integer and
be all the natural numbers less than
and relatively prime to
. If
prove that
must be either a prime number or a power of
.
Solution 1
We use Bertrand's Postulate: for is a positive integer, there is a prime in the interval
.
Clearly, must be equal to the smallest prime
which does not divide
. If
, then
is a prime since the common difference
is equal to
, i.e. all positive integers less than
are coprime to
. If, on the ther hand,
, we find
to be a power of
: the positive integers less than
and coprime to it are precisely the odd ones. We may thus assume that
. Furthermore, since
, the positive integers less than
and coprime to it cannot be
alone, i.e.
.
By Bertrand's Postulate, the largest prime less than is strictly larger than
, so it cannot divide
. We will denote this prime by
. We know that
. It's easy to check that for
there is a prime
strictly between
.
, so, in particular,
. On the other hand, if
, the two largest primes
which are smaller than
satisfy
(again, Bertrand's Postulate), so
so, once again, we have
(this is what I wanted to prove here).
Now, , and all the numbers
are smaller than
(they are smaller than
, which is smaller than
, according to the paragraph above). One of these numbers, however, must be divisible by
. Since our hypothesis tells us that all of them must be coprime to
, we have a contradiction.
This solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [1]
Solution 2
Let . Then we have
. Since
, so
is the largest positive integer smaller than
and co-prime to
. Thus,
and
which shows
and so
divides
. We make two cases.
Case 1:
is odd. Then
. So, every divisor of
is co-prime to
too, so is
. Thus, there is a
such that
which implies
. Therefore, in this case,
and we easily find that all numbers less than
are co-prime to
, so
must be a prime.
Case 2:
is even. But then
and also
is ruled out. So
. Say,
. Then,
divides
. If
is odd,
and
forcing
, contradiction! So,
with
. If
for some
, then
. So, again
for a
. If
is odd, then
and thus,
. Similarly, we find that actually
must occur. We finally have,
. But then all odd numbers less than
are co-prime to
. So,
does not have any odd factor i.e.
for some
.
This solution was posted and copyrighted by ngv. The original thread for this problem can be found here: [2]
Solution 3
We use Bonse's Inequality: , for all
,
.
Let denote the smallest prime which does not divide
.
Case 1) . This implies
is a prime.
Case 2)
. This implies
for some
.
Case 3)
. Since
, we have that
. Therefore
, but
.
Case 4)
. Write
. We have
. Hence
, a contradiction since
.
This solution was posted and copyrighted by SFScoreLow. The original thread for this problem can be found here: [3]
Solution 4
Clearly, . Now let
be the smallest prime number which is not a divisor of
. Hence,
, and the common difference
. Observe that since
, we have that
, or
. This means that all prime factors of
are prime factors of
. However, due to the minimality of
, all primes factors of
are prime factors of
. By the Euclidean algorithm, the only prime factors of
are
, so
or
, by the theory of Fermat primes. We will now do casework on
.
Case 1:
This case is relatively easy.
, so all numbers less than
must be relatively prime to
. However, if
, where
and
, observe that
is not relatively prime to
, so
must be prime for this case to work.
Case 2: and
.
This case is somewhat tricky. Observe that
is even. Since
, we have that all numbers less than
which are odd are relatively prime to
. However, if
has a odd divisor
, clearly
is not relatively prime to
, so
must be a power of two.
Case 3: .
Note that
must be a divisor of
, so
cannot be a multiple of
for any
. I will contradict this statement. First, I claim that
for all integers
.
is trivial, so let me show that
has only solutions less than or equal to
. Since
is a multiplicative function, observe that
cannot be a multiple of a prime greater than
, because for such primes
we have that
, which is contradiction. Hence,
is just composed of factors of
and
. If it divides both, and is of the form
for
and
positive, we get that we need
, so
and
in this case. If it is of the form
, we get
. And if it is of the form
, we get
.
,
, and
are all less than or equal to
, so
. Now we're almost done. Since
, the number
must be in this sequence. However,
is of the form
, which is a multiple of
, and we have contradiction, so we are done.
This solution was posted and copyrighted by va2010. The original thread for this problem can be found here: [4]
Solution 5
Clearly that . Let
then
We can see that if
is a prime then
satisfies the condition. We consider the case when
is a composite number. Let
be the smallest prime divisor of
then
. Note that
for all prime
since
for all
. Therefore, if
then there will exists
such that
or
, a contradiction since
. Thus,
. We consider two cases:
If then
. Hence,
. This means there exists a prime
such that
. Since
so we get
or
, a contradiction since
. Thus,
or
.
If then all odd numbers
are relatively prime to
. This can only happen when
.
If then
since
. Thus,
or there exist a prime
such that
. Note that
so
, a contradiction.
Thus, must be either a prime number or a power of
.
This solution was posted and copyrighted by shinichiman. The original thread for this problem can be found here: [5]
See Also
1991 IMO (Problems) • Resources | ||
Preceded by Problem 1 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 3 |
All IMO Problems and Solutions |