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

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

  • 4
    $\begingroup$ 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 $\endgroup$ – Shivang jindal Jan 29 '15 at 18:57
  • $\begingroup$ 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. $\endgroup$ – user26486 Feb 3 '15 at 21:44
  • $\begingroup$ 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). $\endgroup$ – 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$.

  • $\begingroup$ 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$. $\endgroup$ – user26486 Feb 3 '15 at 21:38
  • $\begingroup$ By definition above, $v_3(x)$ is the maximum power of $3$ that divides $x$. $\endgroup$ – Larry Freeman Feb 3 '15 at 21:46
  • $\begingroup$ 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$. $\endgroup$ – user26486 Feb 3 '15 at 21:52
  • $\begingroup$ 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$ $\endgroup$ – Larry Freeman Feb 3 '15 at 22:00
  • 1
    $\begingroup$ No. You're wrong. $v_p(n)=w\iff n=p^wk, p\not\mid k$. $\endgroup$ – user26486 Feb 3 '15 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.