Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(Created page with "3. Determine all integers <math>n\textgreater1</math> such that <math>\frac{2^n+1}{n^2}</math> is an integer.")
 
Line 1: Line 1:
−
3. Determine all integers <math>n\textgreater1</math> such that <math>\frac{2^n+1}{n^2}</math> is an integer.
+
==Problem==
 +
Determine all integers <math>n > 1</math> such that <math>\frac{2^n+1}{n^2}</math> is an integer.
 +
 
 +
==Solution 1==
 +
Let <math> N = \{ n\in\mathbb{N} : 2^n\equiv - 1\pmod{n^2} \}</math> be the set of all solutions and <math> P = \{ p\text{ is prime} : \exists n\in N, p|n \}</math> be the set of all prime factors of the solutions.
 +
 
 +
It is clear that the smallest element of <math> P</math> is 3.
 +
Assume that <math> P\ne\{3\}</math> and let's try to determine the second smallest element <math> q = \min (P\setminus\{3\})</math>.
 +
 
 +
Let <math> n\in N</math> be a multiple of <math> q</math>. It is important to notice that <math> 9\not|n</math> (otherwise it is easy to get that any power of <math> 3</math> divides <math> n</math>, a non-sense). Therefore, <math> n = 3^t n'</math> where <math> t = 0</math> or <math> 1</math> and <math> n'</math> does not have prime divisors smaller than <math> q</math>.
 +
Since <math> 2^{2n}\equiv 1\pmod{q}</math>, the multiplicative order <math> r = ord_q(2)</math> of 2 modulo <math> q</math> divides <math> 2n</math>. Moreover, <math> r</math> must be even, since otherwise we would have <math> 2^n \equiv 1\pmod{q}</math>, a contradiction to the required <math> 2^n \equiv - 1\pmod{q}</math>.
 +
Since <math> r < q</math> we must have <math> r = 2</math> or <math> 2\cdot 3 = 6</math>. But the numbers <math> 2^2 - 1 = 3</math> and <math> 2^6 - 1 = 63</math> deliver only one new prime factor <math> 7</math>, implying that <math> q = 7</math>. However, in this case <math> r = ord_7(2) = 3</math>, a contradiction. This contradiction proves that <math> P = \{3\}</math> and thus <math> N = \{1,3\}</math>.
 +
 
 +
This solution was posted and copyrighted by maxal/orl. The original thread for this problem can be found here: [https://aops.com/community/p1225144]
 +
 
 +
==Solution 2==
 +
Let <math> p</math> be the smallest prime divisor of <math> n</math>. It is easy to check that, <math> n=3</math> is obviously solution. Let <math> p^{a} || n</math> . <math> p | 2^{2n}-1</math> and <math> p | 2^{p-1} - 1</math> (By the fermat's theorem), we obtain that <math> p=3</math>. It is also obvious that n is an odd number.
 +
Lemma: For all <math> n</math> positive integers, <math> 2</math> is a primitive root modulo <math> 3^{n}</math>.
 +
<math> 3^{2a} | 2^{2n} - 1</math>. Using the lemma, we get that <math> \phi(3^{2a}) | 2n</math>. Using the power of three, we obtain that <math> 3^{2a-1} | 3^{a}</math>. This is only possible when <math> a \geq 2a-1</math>. So <math> a=1</math>. Now <math> q</math> be the second smallest prime divisor of <math> n</math>. <math> (2n,q-1) = 2 , 6</math>. If this equals to 2, we get <math> q=3</math> which is a contradiction.If <math> (2n,q-1) = 6</math> then <math> q|63</math>. We know that <math> q</math> is different from <math> 3</math>. Hence <math> q</math> must be <math> 7</math>. But this is impossible since
 +
<math> 2^{n} +1\equiv 2\mod 7</math> when <math> n</math> is divisible by <math> 3</math>. Hence the answer is <math> n = 3</math>.
 +
 
 +
This solution was posted and copyrighted by grumpyorum. The original thread for this problem can be found here: [https://aops.com/community/p1707739]
 +
 
 +
==Solution 3==
 +
Trivially <math>n=1</math> is a solution. Now assume <math>n\neq 1</math> and define <math>\pi(n)</math> to be the smallest prime divisor of <math>n</math>. Let <math>\pi(n)=p\neq 2</math>. 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 <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*}
 +
 
 +
However <math>2^n+1\equiv 8^{n_1}+1\equiv 2\pmod{7}</math> contradiction.
 +
 
 +
The solutions are henceforth <math>n=1, 3</math>.
 +
This solution was posted and copyrighted by binomial-theorem. The original thread for this problem can be found here: [https://aops.com/community/p3217312]
 +
 
 +
==Solution 4==
 +
et <math>n>1</math> and <math>p</math> be the smallest prime factor of <math>n</math>.Then <math>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}</math>.
 +
Thus <math>n=3^x*y</math> for some positive <math>x</math> and <math>y</math>.
 +
Also <math>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}</math>.
 +
 
 +
Thus <math>n=3y</math> for some positive integer <math>y</math>.
 +
Now let <math>y>1</math> and <math>q</math> be the smallest prime divisor of <math>y</math>.Then we can deduce that <math>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}</math>(Note that <math>\text{gcd}(n,q-1)</math> is <math>1</math> or <math>3</math>).
 +
 
 +
But this gives <math>7|2^n+1</math> which is false as <math>2^n+1</math> leaves remainders <math>1,2,4</math> modulo <math>7</math>.
 +
 
 +
Thus <math>y=1</math> and <math>\boxed{n=3}</math> if <math>n>1</math>.
 +
 
 +
Thus the solutions are <math>\boxed{n=1}</math> and <math>\boxed{n=3}</math>
 +
 
 +
This solution was posted and copyrighted by sayantanchakraborty. The original thread for this problem can be found here: [https://aops.com/community/p3494946]
 +
 
 +
Many more solutions can be found in the thread in Contest Collections.
 +
 
 +
== See Also == {{IMO box|year=1990|num-b=2|num-a=4}}

Revision as of 13:44, 30 January 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.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_IMO_Problems/Problem_3&oldid=144073"