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 thenWe 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 |