The possible values of $n$ that i am able to find is $n=1$ and $n=3$, so there are two solutions and this seems to be the answer to this problem. But now we have to prove that no more of such $n$ exists, and thus the proof reduces to: Proving that $n^2$ does not divides $2^n+1$ for any $n \gt 3$. Does anybody know how to prove this? |
|||||||||||
|
|
This was Problem 3 (first day) of the 1990 IMO. A full solution can be found here. |
|||||||||
|
|
Andre's modification of a wrong answer :) If $n=3^k$, then $$2^n+1=2^{3^k}+1=2^{3 \cdot 3^{k-1}}+1= (2^{3^{k-1}}+1)( 2^{2 \cdot 3^{k-1}}-2^{ \cdot 3^{k-1}}+1) $$ The second bracket is never divisible by $9$, thus by induction one can prove that $3^{2k-1}$ doesn't divide $2^n+1$. Note: Since Geoff's answer was wrong, and this post doesn't make too much sense anymore, a simple observation: If $n \neq 1$, then $3|n$. Indeed let $p$ be the smallest prime divisor of $n$. Then $2^{p-1} \equiv 1 \mod p$ and $2^{2n} \equiv (-1)^2 \equiv 1 \mod p$. Thus $2^d \equiv 1 \mod p$ where $d=gcd(p-1,2n)$. But no prime factor of $p-1$ can divide $n$, since $p$ is the smallest one, thus $gcd(p-1,n)=1$. Hence $d |2$. $2^d \equiv 1 \mod p$ implies now that $p=3$. This proves that $n=3^km$ for some $k \geq 1$ and $m $ relatively prime to $3$. I wonder if the first argument can be modified for this case: $$2^n+1=2^{3^km}+1=2^{3 \cdot 3^{k-1}m}+1= (2^{3^{k-1}m}+1)( 2^{2 \cdot 3^{k-1}m}-2^{ \cdot 3^{k-1}m}+1) $$ Since $9$ doesn't divide the second bracket we get that $3^{2k-1}$ must divide $(2^{3^{k-1}m}+1)$ and repeating I think we get $3^{k}$ divides $2^m+1$... It is easy to prove that $2^m \equiv -1 \mod 9$ implies $3 |m$ (this follows from $2^3 \equiv -1 mod 9$ and $ord(2)=6$). Hence $k=1$, and we must have $n=3 m$ with $gcd(3,m)=1$... Now, lets try the same again. Suppose by contradiction $m \neq 1$. Let $q$ be the smallest prime factor of $m$. Then $2^d \equiv 1 \mod q$ where $d=gcd(q-1,2n)$. But no prime factor of $p-1$ can divide $n$, excepting $3$, Hence $d |6$. This implies that $$2^6 \cong 1 \mod q \,.$$ Thus, the only possible values of $q$ is $q=7$. But this is not possible since $2^{3m}+1 \equiv 1+1 \mod 7$, thus $7$ cannot divide $2^n+1$. |
|||||||||||||||
|
|
I've translated the handling of the problem into a certain notation, which I find very useful for formal algebraic manipulation of exponential diophantine problems, and provide a solution in that formalism. The Woeginger-solution was already linked by André Nicolas so my proposed way of solving this is now only for that reader who might be interested into that -hopefully: much general- formalism. Here is the link so far. (I'm a bit lazy to recode the text into latex/mathjax here after the original fiddling with word/word-to-pdf. Maybe I can put it into mathjax after the weekend, if there is any interest at all) |
|||
|
|
