Difference between revisions of "1990 IMO Problems/Problem 3"

Revision as of 17:15, 7 August 2021

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.

@@ Line 27: / Line 27: @@
 Now if <math>r\neq 2\mid n</math> then we can't have <math>r\mid p-1</math> because then <math>r\le p-1</math> contradiction. Therefore <math>r=2</math> and since <math>n</math> is odd <math>\gcd(2n, p-1)=2</math>. Hence<cmath>p\mid 2^2-1 \implies p=3</cmath>Let <math>v_3(n)=k</math>. By lifting the exponent we must have<cmath>v_3(2^n+1)=1+k\ge v_3(n^2)=2k \implies k=1</cmath>Let <math>n=3n_1</math>. <math>n_1=1</math> is a solution (<math>2^3+1=3^2=9</math>). Assume <math>n_1\neq 1</math> and let <math>\pi(n_1)=q\neq 3</math>. By Chinese Remainder Theorem since <math>q\neq 3</math> 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*}
+<cmath>\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*}</cmath>
 However <math>2^n+1\equiv 8^{n_1}+1\equiv 2\pmod{7}</math> contradiction.

1990 IMO (Problems) • Resources
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4
All IMO Problems and Solutions

Page

Toolbox

Search