# Find all positive integers $n$ for some given condition.

Find all positive integers $n>1$ such that $n^2$ divides $2^n+1$

I found that $n$ is of the form $6k+3$.

• You know lifting the exponent lemma?. This problem is trivial using the theorem. If you don't know the lemma, read this article : artofproblemsolving.com/Resources/Papers/LTE.pdf If you want other solutions then, cs.cornell.edu/~asdas/imo/imo/isoln/isoln903.html – Shivang jindal Jan 29 '15 at 18:57
• ArtOfProblemSolving has some solutions here. See the official solution, except you can prove that $k=1$ without using the lemma and trivially using LTE instead. – user26486 Feb 3 '15 at 21:44
• The official solution I gave in the comment above is the solution I think would best fit an answer to this question, but I won't post it, since it is already written there (except, as I said, prove that $k=1$ by using LTE instead). – user26486 Feb 4 '15 at 0:28

The only answer is $n=3$

(1) Since $n$ divides $2^n + 1$, $n$ is odd. Let $p$ be the smallest prime divisor of $n$

(2) Let $a$ be the smallest positive integer such that $2^a \equiv -1 \pmod p$. $a$ must exist since $2^n \equiv -1 \pmod p$

(3) Let $b$ be the smallest positive integer such that $2^b \equiv 1 \pmod p$. $b$ must exist and $b < p$ since $2^{p-1} \equiv 1 \pmod p$

(4) There exists $q,r$ such that $n = qb+r$ and $0 \le r < b$ so that $-1 \equiv 2^n \equiv (2^b)^q2^r \equiv 2^r \pmod p$ and $a \le r < b$ and $r > 0$

(5) There exists $h,k$ such that $n = ha+k$ and $0 \le k < a$ so that $-1 \equiv 2^n \equiv (2^a)^h2^k \equiv (-1)^h2^k \pmod p$

(6) $k=0$ since if $k > 0$ then $h$ cannot be even since then $2^k \equiv -1 \pmod p$ and $k < a$ and $h$ cannot be odd since $2^k \equiv 1 \pmod p$ and $k < a \le r < b$

(7) Since $k=0$, $a | n$. Since $a < p$, $a=1$ but if $2^1 \equiv -1 \pmod p$, $p=3$

(8) From the article cited by Shivang, we have:

Let $v_p(x)$ be the greatest power in which prime $p$ divides $x$.

Theorem 2: (Second form of LTE) Let $x,y$ be two integers, $n$ be an odd positive integer and $p$ an odd prime such that $p|(x+y)$ and none of $x$ and $y$ is divisible by $p$, we have:

$$v_p(x^n + y^n) = v_p(x+y) + v_p(n)$$

(9) Let $x=2$, $y=1$

(10) By Theorem 2: $v_3(2^n + 1) = v_3(2^n + 1^n) = v_3(2+1) + v_3(n) = 1 + v_3(n)$

(11) So, there exists $w$ with odd $r,s$ such that $3^wr = n$ and $3 \nmid r$ and $3^{w+1}s = 2^n + 1$ and $3 \nmid s$. Since $n^2 | 2^n+1$, it follows that $3^{2w}r^2 |\, (3^{w+1}s)$ but this is only possible if $2w = w+1$ so that $w=1$.

(12) So, we have $n=3r$. Asume $r > 1$ Let $p$ be the least prime that divides $r$. Since $r | (2^n+1)(2^n - 1) = 2^{2n} - 1$, so $2^{2n} \equiv 1 \pmod p$ and using Fermat's Little Theorem gives us $2^{p-1} \equiv 1 \pmod p$. Therefore $2^{\gcd(2n,p-1)}\equiv 1 \pmod p$. Since $p$ is the least prime, $(p-1) \nmid n$, $\gcd(2n,p-1)=2$

(13) But if $2^2\equiv 1\pmod p$, then $p=3$ which is impossible since $3 \nmid r$ so $r=1$.

(14) $3^2s = 2^3 + 1$ is only true if $s=1$. So, the only solution is $n=3$.

• Could you elaborate on your (11) claim that $n$ is a power of $3$? I can see from $(10)$ that $1+v_3(n)\ge 2v_3(n)\iff v_3(n)\le 1\iff v_3(n)=1$ (since $3\mid n$, we have $v_3(n)\ge 1$). Thus $n=3k, 3\not\mid k, 2^n+1=9m, 3\not\mid m$. – user26486 Feb 3 '15 at 21:38
• By definition above, $v_3(x)$ is the maximum power of $3$ that divides $x$. – Larry Freeman Feb 3 '15 at 21:46
• That does not explain $n$ being a complete power of $3$ without any other prime divisors. Based on (10) I can only claim that $n=3^wk, k\not\mid 3, 2^n+1=3^{w+1}m, m\not\mid 3$. – user26486 Feb 3 '15 at 21:52
• I am using Theorem 2 to show that $v_3(2^n + 1) = 1+v_3(n)$. This is true if $n$ is an odd, positive integer and $p$ is an odd prime such that $p|(x+y)$ and none of $x$ and $y$ are divisible by $p$. Let $w = v_3(n)$ Then, $3^{w+1} = 2^n+1$ since $v_3(2^n+1) = 1+w$ – Larry Freeman Feb 3 '15 at 22:00
• No. You're wrong. $v_p(n)=w\iff n=p^wk, p\not\mid k$. – user26486 Feb 3 '15 at 22:12