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"

m (→‎Solution 3)
(→‎Solution 4)
 
(One intermediate revision by one other user not shown)
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:
 
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.
 
However <math>2^n+1\equiv 8^{n_1}+1\equiv 2\pmod{7}</math> contradiction.
Line 35: Line 38:
  
 
==Solution 4==
 
==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>.
+
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)}-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>.
 
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>.
 
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>.

Latest revision as of 18:07, 25 July 2024

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)}-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=223662"