1990 IMO Problems/Problem 3

Revision as of 09:26, 19 June 2021 by Drbao (talk | contribs) (Solution 3)

Problem

Determine all integers $n > 1$ such that $\frac{2^n+1}{n^2}$ is an integer.

Solution 1

Let $N = \{ n\in\mathbb{N} : 2^n\equiv - 1\pmod{n^2} \}$ be the set of all solutions and $P = \{ p\text{ is prime} : \exists n\in N, p|n \}$ be the set of all prime factors of the solutions.

It is clear that the smallest element of $P$ is 3. Assume that $P\ne\{3\}$ and let's try to determine the second smallest element $q = \min (P\setminus\{3\})$.

Let $n\in N$ be a multiple of $q$. It is important to notice that $9\not|n$ (otherwise it is easy to get that any power of $3$ divides $n$, a non-sense). Therefore, $n = 3^t n'$ where $t = 0$ or $1$ and $n'$ does not have prime divisors smaller than $q$. Since $2^{2n}\equiv 1\pmod{q}$, the multiplicative order $r = ord_q(2)$ of 2 modulo $q$ divides $2n$. Moreover, $r$ must be even, since otherwise we would have $2^n \equiv 1\pmod{q}$, a contradiction to the required $2^n \equiv - 1\pmod{q}$. Since $r < q$ we must have $r = 2$ or $2\cdot 3 = 6$. But the numbers $2^2 - 1 = 3$ and $2^6 - 1 = 63$ deliver only one new prime factor $7$, implying that $q = 7$. However, in this case $r = ord_7(2) = 3$, a contradiction. This contradiction proves that $P = \{3\}$ and thus $N = \{1,3\}$.

This solution was posted and copyrighted by maxal/orl. The original thread for this problem can be found here: [1]

Solution 2

Let $p$ be the smallest prime divisor of $n$. It is easy to check that, $n=3$ is obviously solution. Let $p^{a} || n$ . $p | 2^{2n}-1$ and $p | 2^{p-1} - 1$ (By the fermat's theorem), we obtain that $p=3$. It is also obvious that n is an odd number. Lemma: For all $n$ positive integers, $2$ is a primitive root modulo $3^{n}$. $3^{2a} | 2^{2n} - 1$. Using the lemma, we get that $\phi(3^{2a}) | 2n$. Using the power of three, we obtain that $3^{2a-1} | 3^{a}$. This is only possible when $a \geq 2a-1$. So $a=1$. Now $q$ be the second smallest prime divisor of $n$. $(2n,q-1) = 2 , 6$. If this equals to 2, we get $q=3$ which is a contradiction.If $(2n,q-1) = 6$ then $q|63$. We know that $q$ is different from $3$. Hence $q$ must be $7$. But this is impossible since $2^{n} +1\equiv 2\mod 7$ when $n$ is divisible by $3$. Hence the answer is $n = 3$.

This solution was posted and copyrighted by grumpyorum. The original thread for this problem can be found here: [2]

Solution 3

Trivially $n=1$ is a solution. Now assume $n\neq 1$ and define $\pi(n)$ to be the smallest prime divisor of $n$. Let $\pi(n)=p\neq 2$. 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 $r\neq 2\mid n$ then we can't have $r\mid p-1$ because then $r\le p-1$ contradiction. Therefore $r=2$ and since $n$ is odd $\gcd(2n, p-1)=2$. Hence\[p\mid 2^2-1 \implies p=3\]Let $v_3(n)=k$. By lifting the exponent we must have\[v_3(2^n+1)=1+k\ge v_3(n^2)=2k \implies k=1\]Let $n=3n_1$. $n_1=1$ is a solution ($2^3+1=3^2=9$). Assume $n_1\neq 1$ and let $\pi(n_1)=q\neq 3$. By Chinese Remainder Theorem since $q\neq 3$ 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 $2^n+1\equiv 8^{n_1}+1\equiv 2\pmod{7}$ contradiction.

The solutions are henceforth $n=1, 3$. This solution was posted and copyrighted by binomial-theorem. The original thread for this problem can be found here: [3]

Solution 4

et $n>1$ and $p$ be the smallest prime factor of $n$.Then $p|2^{2n}-1,p|2^{p-1}-1 \Rightarrow p|2^{\text{gcd}(2n,p-1)}=2^2-1=3\Rightarrow \boxed{p=3}$. Thus $n=3^x*y$ for some positive $x$ and $y$. Also $n^2|2^n+1 \Rightarrow 2x=v_3(n^2) \le v_3(2^n+1)=v_3(3)+v_3(n)=x+1 \Rightarrow \boxed{x=1}$.

Thus $n=3y$ for some positive integer $y$. Now let $y>1$ and $q$ be the smallest prime divisor of $y$.Then we can deduce that $q|2^{\text{gcd}(2n,q-1)}-1=2^{2\text{gcd}(n,q-1)}-1=2^6-1=63=7*3^2 \Rightarrow \boxed{q=7}$(Note that $\text{gcd}(n,q-1)$ is $1$ or $3$).

But this gives $7|2^n+1$ which is false as $2^n+1$ leaves remainders $1,2,4$ modulo $7$.

Thus $y=1$ and $\boxed{n=3}$ if $n>1$.

Thus the solutions are $\boxed{n=1}$ and $\boxed{n=3}$

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