Approach by maxal: 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\}$.

Let us assume n > 1. Obviously n is odd. Let p ≥ 3 be the smallest prime divisor of n. In this case (p − 1, n) = 1. Since 2n + 1 | 22n − 1, we have that p | 22n − 1. Thus it follows from Fermat’s little theorem and elementary number theory that p | (22n − 1, 2p−1 − 1) = 2(2n,p−1) − 1. Since (2n, p − 1) ≤ 2, it follows that p | 3 and hence p = 3. Let us assume now that n is of the form n = 3kd, where 2, 3 d. We first prove that k = 1. Lemma. If 2m − 1 is divisible by 3r, then m is divisible by 3r−1. Proof. This is the lemma from (SL97-14) with p = 3, a = 22, k = m, α = 1, and β = r. Since 32k divides n2 | 22n − 1, we can apply the lemma to m = 2n and r = 2k to conclude that 32k−1 | n = 3kd. Hence k = 1. Finally, let us assume d > 1 and let q be the smallest prime factor of d. Obviously q is odd, q ≥ 5, and (n, q−1) ∈ {1, 3}. We then have q | 22n−1 and q | 2q−1 − 1. Consequently, q | 2(2n,q−1) − 1 = 22(n,q−1) − 1, which divides 26 −1 = 63 = 32 · 7, so we must have q = 7. However, in that case we obtain 7 | n | 2n + 1, which is a contradiction, since powers of two can only be congruent to 1,2 and 4 modulo 7. It thus follows that d = 1 and n = 3. Hence n > 1 ⇒ n = 3. It is easily verified that n = 1 and n = 3 are indeed solutions. Hence these are the only solutions.

ramakrishna wrote: $ \cdots$ Since 2n + 1 | 22n − 1, $ \cdots$ I don't understand this perhaps you could use latex?

thanks for such a nice solution

That's the official solution (see the attachment). ramakrishna copied it and so the LaTeX formulas got lost.

Attachments:
IMO1990.3.pdf (79kb)

Another approach: 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$.

FelixD, where did you find the official solution ?

The "official" solution is that in the shortlist, http://www.artofproblemsolving.com/Forum/download/file.php?id=1042, pp. 45-46, which is somewhat different from those posted here.

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

Click to reveal hidden text

because $n^2|2^n+1$ so $n$ is odd. then $n=\prod {{p_i}^{{\alpha _i}}} $ with $p_i $ odd $n^2|2^n+1$ lead to $v_p(n^2)<v_p(2^n+1)$ but,use the lifting exponent we have $v_p(2^n+1)=v_p(2^n-(-1)^n)=v_p(3)+v_p(n)$ if $p_i \ge 5$ then $v_p(3)=0$. so that we have $v_p(n^2) \le v_p(n)$ wich $n=1$ if p=3 we have $v_3(n^2) \le 1+ v_3 (n) $ then $v_3(n)=0;1$ then $n=1,3$ summary,we have n=1,n=3

Generalisation: if $p$ is an odd prime, $n>1$ and $(p-1)^n+1$ is divisible by $n^{p-1}$, then $p=n=3$.

nnosipov,you missed the case $n=p=2$ It was a problem from Imo with the additional condition $n<2p$.But we can even eliminate the case $n<2p$ and much more generally prove the fact.

Some approaches of the following generalisation? Let $a,b>1$ positive integers such that $\dfrac{a^b+1}{b^a}$ is an integer. Find all $a,b$.

Victory.US wrote: ...but,use the lifting exponent we have $v_p(2^n+1)=v_p(2^n-(-1)^n)=v_p(3)+v_p(n)$... No, this is not true. If you want to use LTE you should make sure that $p|2+1=3,$ but this is not true for any prime $p,$ and so you can't use LTE here.

Well let me post my solution Lemma: If $n|2^n+1,n=3^k$ Proof: Obviously $n$ odd,let $p$ be the smallest prime factor of $n,$then $2^{2n}\equiv 1\mod p,2^{p-1}\equiv 1\mod p\implies 2^{gcd(2n,p-1)}\equiv 1\mod p$ Since $p$ is the smallest prime factor,no prime of $p-1$ will be shared with $n,$so $gcd(2n,p-1)=2$ Therefore $2^2\equiv 1\mod p\implies p=3$ and so let $n=3^kl$ where $3\not| l,$but if $l>1$ similarly the smallest prime factor of $l$ is $3,$contradiction. Thus $n=3^k$ Now get back to original problem and we shall use Lte,so $v_3(n^2)=2k$ and $v_3(2^n+1)=k+1$ If $n>1,k\ge 1$ and we get $2k\le k+1\implies k\le 1$ implying $k=1$ Then the only solutions $n=\boxed {1,3}$

Very nice solution.

mathmdmb wrote: $v_3(2^n+1)=k+1$ can you tell me why?

FBI__ wrote: can you tell me why? Sure. This comes from Lifting The Exponent lemma (see here). For a prime $p$, if $p \mid x+y$, neither $x$ nor $y$ is divisible by $p$, and $n$ is an odd positive integer, then \[v_p(a^n+b^n)=v_p(n)+v_p(a+b).\] mathmdmb proved that $n = 3^k$, so (since $3 \mid 2+1$) \[v_3(2^n+1)=v_3(2^{3^{k}} + 1) = v_3(3^k)+v_3(2+1)=k+1.\]

Thank you

mathmdmb wrote: Well let me post my solution Lemma: If $n|2^n+1,n=3^k$ Proof: Obviously $n$ odd,let $p$ be the smallest prime factor of $n,$then $2^{2n}\equiv 1\mod p,2^{p-1}\equiv 1\mod p\implies 2^{gcd(2n,p-1)}\equiv 1\mod p$ Since $p$ is the smallest prime factor,no prime of $p-1$ will be shared with $n,$so $gcd(2n,p-1)=2$ Therefore $2^2\equiv 1\mod p\implies p=3$ and so let $n=3^kl$ where $3\not| l,$but if $l>1$ similarly the smallest prime factor of $l$ is $3,$contradiction. Thus $n=3^k$ Now get back to original problem and we shall use Lte,so $v_3(n^2)=2k$ and $v_3(2^n+1)=k+1$ If $n>1,k\ge 1$ and we get $2k\le k+1\implies k\le 1$ implying $k=1$ Then the only solutions $n=\boxed {1,3}$ See IMO 2000/5 if I'm correct to see this is totally wrong.

I claim that the only solution is when $\boxed{n = 3}$. Let $p$ be the smallest prime dividing $n$. Then \[2^{2n} \equiv 1 \pmod p \text{ and } 2^{p - 1} \equiv 1 \pmod p \implies o(2)_p \mid \gcd(2n, p - 1) \in \{1, 2\}. \]Now if $o(2)_p = 1$ we obtain no solution. If, however, $o(2)_p = 2$, then $\boxed{p = 3}$. Lemma: $2$ is always a primitive root modulo $3^N$ for any $N \in \mathbb{Z}_{>0}$. If now $3^{\alpha} \parallel n$ for some $\alpha$, then $3^{2 \alpha} \parallel n^2$ and we have that \[2^{\phi(3^{2 \alpha})} \equiv \pmod{3^{2 \alpha}} \text{ and } 2^{2n} \equiv 1 \pmod{3^{2 \alpha}} \implies \phi(3^{2 \alpha}) \mid 2n \implies v_3(2n) \geq v_3(\phi(3^{2 \alpha})) \implies \alpha \geq 2 \alpha - 1 \implies \alpha = 1. \]Therefore $3 \parallel n$. If now $q$ is the second smallest prime that divides $n$, we must have again that $o(2)_q \mid \gcd(2n, q - 1) \in \{1, 2, 6\}$. Here $o(2)_q = 1, 2$ provides us with the information that $q = 1$ and $q = 3$, both of which are contradictions. Hence in our final option $o(2)_q = 6 \implies \boxed{q = 7}$. However notice that $2^n + 1 \equiv 8^N + 1 \equiv 2 \pmod 7$, which is impossible. Therefore no other prime may divide $n$ but $3$, providing us with $\boxed{n = 3}$ as the only valid solution. $\blacksquare$

No $n>1$ condition given to me The answer is $\boxed{n=1,3}$. Begin by noting that $n=1$ works. Henceforth assume $n \neq 1$. Clearly, $n$ is odd by parity arguments. Denote the smallest prime factor of $n$ as $p$. We have \[p \mid 2^n+1 \implies \operatorname{ord}_p(2) \mid \gcd(p-1,2n)\] If $p-1 \mid n$, this contradicts minimal condition, so we must have $\operatorname{ord}_p(2)=2$. This means that \[2^2 \equiv 1 \pmod{p} \implies p=3.\] Then, \[\nu_3(n^2) = 2\nu_3(n) \le \nu_3(2^n+1) = \nu_3(2+1) + \nu_(n)\]\[\iff \nu_3(n) \le 1.\] We know $3$ divides $n$, so we have that exactly one power of $3$ divides $n$. Denote the second-smallest prime dividing $n$ as $q$. We have \[q \mid 2^n+1 \implies \operatorname{ord}_q(2) \mid \gcd(q-1,2n).\] Thus, $\operatorname{ord}_q(2) = 2, 6$. Caseworking shows that $q=3,7$, but neither works. Hence, $n$ contains only prime factors of $3$. This implies the only solution is $n = 3$.

Suppose FTSOC $n$ has at least 2 distinct prime divisors. Let the smallest be $p_1 > 2$. Then \[\operatorname{ord}_{p_1} 2 \mid \gcd(2n,p_1-1) = 2 \implies p_1 = 3.\]In particular, LTE gives us \[v_3(n^2) \leq v_3(2^n+1) \implies 2 v_3(n) \leq 1 + v_3(n) \implies v_3(n) = 1.\] Suppose the second smallest is $p_2 > 3$. Then \[\operatorname{ord}_{p_2} 2 \mid \gcd(2n,p_2-1) = 2,6 \implies p_2 = 7.\]However, 7 never divides $2^n+1$ for any $n$, contradiction. Hence we extract our only answers $n = \boxed{1,3}$. $\blacksquare$

I think that's missing a little detail: How do you know that $3$ divides $n$ only once? Otherwise, you could have something like $$\gcd(2n,p_2-1)=18.$$

ddot1 wrote: I think that's missing a little detail: How do you know that $3$ divides $n$ only once? Otherwise, you could have something like $$\gcd(2n,p_2-1)=18.$$ Follows from the LTE statement - $0 < v_3(n) \leq 1$.

Oh, duh - sorry, I didn't read it carefully enough.

The answer is $n=1,3$. We show that there are no other solutions. Since $n$ must be odd, assume $n \geq 5$. Let $p$ be the least prime factor of $n$. We have $p > 2$ since $n$ is odd. Furthermore, $2^n + 1 \equiv 0 \implies 4^n \equiv 1 \pmod{p}$. We claim the order of $4$ mod $p$ is $1$. This is because the order must divide $\gcd{n, p-1}$, which must equal $1$ otherwise $\gcd{n, p-1}$ must have smaller prime factors which also divide $n$, contradicting $p$'s minimality. Thus, $4 \equiv 1 \pmod{p}$, so $p = 3$. In order for $n^2$ to divide $2^n + 1$, we must have $\nu_3(n^2) = 2\nu_3(n) \leq \nu_3(2^n + 1)$. Since $3 \mid 2 + 1$, using the lifting the exponent lemma yields $\nu_3(2^n + 1) = 1 + \nu_3(n)$. We then conclude that $\nu_3(n) \leq 1$, but since $3$ is the smallest prime factor of $n$, we must have $\nu_3(n) = 1$. Now, we write $n = 3k$ for some $k$ not divisible by $2$ or $3$. Since $n \geq 5$, we have $k > 1$ and we can let $p$ be the smallest prime factor of $k$. But similarly to before, we see that $2^{6k} \equiv 1 \pmod{p}$ and thus $64 \equiv 1 \pmod{p}$. This means $p \mid 63$. Since $p \geq 5$, we must have $p = 7$. This tells us that $n^2$ is divisible by $7$. However, $2^n + 1 \equiv 8^k + 1 \equiv 2 \pmod{7}$, so we are done.

Say $p$ is the smallest prime dividing $n$, so we have $2^n + 1 \equiv 0 \mod{p} \implies 2^{2n} \equiv 1\mod{p}$. Clearly $p \neq 2$. Let $k$ denote the order of $2 \mod{p}$. Observe that $k \mid 2n$, and since $2^{p - 1} \equiv 1 \mod{p}$, we have $k \mid (2n, p - 1) \implies k = 1, 2$. $k = 1$ is impossible, which means $k = 2 \implies 2^2 \equiv 1 \mod{p} \implies p = 3$. If $q$ is the next smallest prime dividing $2^n + 1$, we have $\text{ord}_q(2) \mid (2n, q - 1) = 3, 6$. $q = 7$ fails upon checking. So $p = 3$ is the only prime dividing $n$. We need $v_3(2^n + 1) \geq v_3(n^2) = 2v_3(n)$, for $n^2 \mid 2^n + 1$. By LTE, $v_3(2^n + 1) = v_3(3) + v_3(n) \implies 1 + v_3(n) \geq 2v_3(n) \implies v_3(n) \leq 1$. $v_3(n) = 0 \implies n = 1$, which clearly works. $v_3(n) = 1 \implies n = 3$, which works as well. So, we are done.

The problem is equivalent to $2^n\equiv -1\pmod{n^2}$. This implies that $2^{2n}\equiv 1\pmod{n^2}$. Also note that $n=1$ is a solution so suppose $n\neq 1$. Now take the smallest prime factor of $n$ (notice that this can’t be $2$). We have that $ord_p(2)\mid 2n$ and also note that $ord_p(2) \le p-1$ so this order must be equal to $2$. Hence $p$=3. Now let $n=3^ab$ where $a\ge 1$ and $b$ is an odd integer. We have: $$\nu_3(n^2)\le \nu_3(2^n+1)$$But we clearly have $\nu_3(n^2)=2a$ and from LTE $\nu_3(2^n+1)=a+1$ hence $a$ must be qual to $1$ so we get that $n=3b$. Plugging this back in, we get that $9k^2\mid 2^{3k}+1$. Now $k=1$ is a solution ($n=3$) so suppose that $k\neq 1$. Let $q$ be the smallest prime factor of $k$ and note that this isn’t $2$ or $3$. We similarly get that $2^{6k}\equiv 1\pmod q$ so $ord_q(2)\mid 6k$ so from minimality this implies $ord_q(2)\mid 6$. Hence $ord_q(2)\in \{3,6\}$. In either case, we get that $q=7$ so $7\mid 2^n+1$ which isn’t possible. Therefore the only solutions are $n=1$ and $n=2$.

Obviously $n$ is odd. Consider the smallest prime $p$ dividing $n$ then order of $p$ modulo $2$ divides $2n$ but not $n$ and it also divides $p-1$ implying the order must be $3$ giving that the smallest prime must be the smallest prime. However $LTE$ gives us that $\nu_3(2^n +1)$ =$\nu_3(n) +1$ which is greater than $2\nu_3(n)$ implying $n=3k$ where $k$ is an odd number not divisible by $3$. Plugging this and using similar order arguments, we get that $7$ divides $2^n +1$ which is false implying $k=1$. Hence $\boxed{n=3}$ is the only solution.

The answer is $n=1,3$ which clearly works. Suppose $n>1$ and let $p_0$ be the smallest prime divisor of $n=p_0^{e_0} p_1^{e_1} \cdots p_k^{e_k}$ with $e_i\geq 0$ for $i>0$. Let $a=\text{ord}_{p_0^2}(2)$. Since $p_0^2\mid 2^n+1$, it follows that $a\nmid n$ and $a\mid 2n$. So $a=2p_0^{f_0}p_1^{f_1} \cdots p_k^{f_k}$ where $f_i\leq e_i$ for all $0\leq i\leq k$. But $a\mid p_0(p_0-1)$ and thus $a\leq p_0(p_0-1)$. From this it follows that $a\in \{2, 2p_0, 2p_i\}$ for some $1\leq i\leq k$. If $a=2$ then $p_0^2\mid 2^2-1=3$ which is absurd. If $a=2p_i$ then from $2p_i\mid p_0(p_0-1)$ it follows that $p_i\mid p_0-1$ which is absurd as well. Thus $a=2p_0$ and $2^{2p_0}\equiv 1\pmod{p_0^2}$. From here it's easy to get that $p_0=3$. So $n=3m$ (by LTE $2v_3(n)\leq v_3(2^n+1)=v_3(2+1)+v_3(n)$ and thus $v_3(n)\leq 1$ and so $3\nmid m$) and $m^2\mid 8^m+1$. We have $m=p_1^{e_1} p_2^{e_2}\cdots p_k^{e_k}$ and let's assume $m>1$ and that $p_1$ is the smallest prime divisor. Let $b=\text{ord}_{p_1^2}(8)$ and as before we get $b\in \{2,2p_1\}$ ($b$ cannot be $2p_i$ because of the same reason as before). If $b=2$ then $p_1^2\mid 8^2-1=3^2\cdot 7$ but this is impossible. So $b=2p_1$ and $p_1^2\mid 8^{2p_1}-1$. From this we get $p_1\mid 8^2-1=3^2\cdot 7$ and so $p_1=7$. Note that $7^2\mid 42799\cdot 7^2=8^7-1$, so $b\leq 7$ but this is a contradiction since $b=2\cdot 7=14$. From this contradiction it follows that $m=1$ and we get the desired solution set.

For min prime p|n p≠3 2^2n = 1 mod p Ord2 mod p | 2n ord 2 mod p = 2,,2n,n,d,2d Here d|n d>1 So it can only be 2,2d As ord2 mod p ≤ p-1 d≥p 2d≥ 2p> p-1 Thus ord 2 mod p ≠ 2d for any d>1 Thus ord 2 mod p = 2 4= 1 mod p So p = 3 Thus 3| n Let q be second smallest prime Ord 2 mod q = 2,2d,6,2n,n,3d Where d|n If d>3 3d>q-1 So d≤3 Now 3 cases d= 3 X d=2 X d= 1 works So ord 2 mod q = 3 Same reasoning with 2d gives ord 2 mod q = 6 Implies q=7 Which is not possible Hence no such q exists Thus only 3|n So 2vp(n) ≤ vp(3) + vp(n) n = 3

We claim the only solution is $n = 3$, which clearly works. Note that $2^{2n} \equiv 1 \pmod{p}$, where $p$ is the smallest prime factor of $n$. But $2^{p-1} \equiv 1 \pmod p$, and thus $2^2 = 2^{\gcd(2n, p-1)} \equiv 1 \pmod{p} \implies \boxed{p = 3}.$ Now note that we have from LTE and $\nu_p$ stuff that $$2\nu_p(n) \le \nu_p(2^n + 1) = \nu_p(3) + \nu_p(n) = 1 + \nu_p(n) \implies \nu_p(n) = 3.$$Now let $n = 2m$ where $\gcd(m, 3) = 1$. Then we have $m^2 \mid 8^m + 1 \implies 8^{2m} \equiv 1 \pmod{q}$ where $q$ is the smallest prime divisor of $m$. But $8^{q-1} \equiv 1 \pmod{q} \implies 8^2 \equiv 1 \pmod{q} \implies q \in \{3, 7\}$. $q = 3$ is impossible because then $\nu_p(n) \ge 2$, and $q = 7$ is impossible because $8^m + 1 \equiv 2 \pmod{7}$, and so $7$ can never divide the numerator. Thus in fact no such prime exists, and $m = 1 \implies \boxed{n = 3}$.

Solution: $\frac{2^n+1}{n^2}$ is an integer $\implies n^2 \mid 2^n+1$ Let $p$ be the smallest prime divisor of $n$ (such a prime exists because $n > 1$). Note that $p \neq 2$ because RHS$=2^n+1 \equiv 1 \pmod 2$ So $p \mid n^2 \mid 2^n+1 \implies p \mid 2^n+1 \iff 2^n+1 \equiv 0 \pmod p \implies 2^n \equiv -1 \pmod p \implies$ $$\boxed{2^{2n} \equiv 1 \pmod p}$$ Also by Fermat's Little Theorem we have that : $$\boxed{2^{p-1} \equiv 1 \pmod p} (\because p \neq 2 \implies gcd(2,p)=1)$$ Hence $$2^{\gcd(2n,p-1)} \equiv 1 \pmod p$$ Note that since $p$ is the smallest prime divisor of $n$ we get that $\gcd(n,p-1)=1$ so $\gcd(2n,p-1)=1 \vee 2$ Note that since $2n \equiv 0 \pmod 2$ and $p-1 \equiv 0 \pmod 2$ we get: $\gcd(2n,p-1)=2 \implies 2^2 \equiv 1 \pmod p \implies p \mid 3 \implies p=3 (\because p$-prime) Hence $3=p \mid n \implies n=3k \implies 9k^2 \mid 8^k+1$ Now suppose that $k >1$ so simmilarly as before let $q$ be the smallest prime divisor of $k$ hence we find that $$8^{\gcd(2k,q-1)} \equiv 1 \pmod q $$ $\gcd(2k,q-1)=2 \implies 8^2 \equiv 1 \pmod q \implies q \mid 63=7 \cdot 3^2 \implies q=3 \vee q=7$ however if $q=7$ then: $7=q \mid 9k^2 \mid 8^k+1 \implies 7 \mid 8^k+1$ but RHS$=8^k+1 \equiv 1+1=2 \pmod 7$ so $7 \nmid RHS \rightarrow \leftarrow$ So $3=q \mid k \implies k=3 \ell \implies$ $$81 \ell^2 \mid 8^{3 \ell}+1$$ Now by taking $\nu_3$ we get: $4+2 \cdot \nu_3(\ell)=\nu_3(81 \ell^2) \leq \nu_3(8^{3 \ell}+1) \stackrel{LTE}{=} \nu_3(8+1)+\nu_3(3 \cdot \ell)=3+\nu_3(\ell) \implies 4+2 \cdot \nu_3(\ell) \leq 3+\nu_3(\ell) \implies$ $$\nu_3(\ell) \leq -1 \rightarrow \leftarrow$$ Hence there doesn't exist a prime $q$ such that $q \mid k$ hence $k=1 \implies n=3$ which obviously works $\blacksquare$

what is r ?