1990 IMO Problems/Problem 3
Problem
Determine all integers such that is an integer.
Solution 1
Let be the set of all solutions and be the set of all prime factors of the solutions.
It is clear that the smallest element of is 3. Assume that and let's try to determine the second smallest element .
Let be a multiple of . It is important to notice that (otherwise it is easy to get that any power of divides , a non-sense). Therefore, where or and does not have prime divisors smaller than . Since , the multiplicative order of 2 modulo divides . Moreover, must be even, since otherwise we would have , a contradiction to the required . Since we must have or . But the numbers and deliver only one new prime factor , implying that . However, in this case , a contradiction. This contradiction proves that and thus .
This solution was posted and copyrighted by maxal/orl. The original thread for this problem can be found here: [1]
Solution 2
Let be the smallest prime divisor of . It is easy to check that, is obviously solution. Let . and (By the fermat's theorem), we obtain that . It is also obvious that n is an odd number. Lemma: For all positive integers, is a primitive root modulo . . Using the lemma, we get that . Using the power of three, we obtain that . This is only possible when . So . Now be the second smallest prime divisor of . . If this equals to 2, we get which is a contradiction.If then . We know that is different from . Hence must be . But this is impossible since when is divisible by . Hence the answer is .
This solution was posted and copyrighted by grumpyorum. The original thread for this problem can be found here: [2]
Solution 3
Trivially is a solution. Now assume and define to be the smallest prime divisor of . Let . Then we have: \begin{eqnarray*} p\mid 2^n+1\mid 2^{2n}-1 \text{ and } p\mid 2^{p-1}-1 \\ \implies p\mid 2^{\gcd(2n, p-1)}-1 \end{eqnarray*}
Now if then we can't have because then contradiction. Therefore and since is odd . HenceLet . By lifting the exponent we must haveLet . is a solution (). Assume and let . By Chinese Remainder Theorem since we have: \begin{eqnarray*} q\mid 8^{n_1}+1\mid 8^{2n_1}-1 \text{ and } q\mid 8^{q-1}-1 \\ \implies q\mid 8^{\gcd(2n_1, q-1)}-1=63 \text{ so } q=7 \end{eqnarray*}
However contradiction.
The solutions are henceforth . This solution was posted and copyrighted by binomial-theorem. The original thread for this problem can be found here: [3]
Solution 4
et and be the smallest prime factor of .Then . Thus for some positive and . Also .
Thus for some positive integer . Now let and be the smallest prime divisor of .Then we can deduce that (Note that is or ).
But this gives which is false as leaves remainders modulo .
Thus and if .
Thus the solutions are and
This solution was posted and copyrighted by sayantanchakraborty. The original thread for this problem can be found here: [4]
Many more solutions can be found in the thread in Contest Collections.
See Also
1990 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |