Question: Find all positive integers $n$ such that $$n^2\mid 2^n+1$$

My solution:

Lemma (Lifting the exponent): Let $v_p(n)$ denote the highest power of a prime $p$ that divides $n$.

That is, $v_p(n)=k$ such that $p^k \mid n$ and $p^{k+1} \nmid n$ . We have the following relation: $$\large v_p(x^n-y^n) = v_p(x-y)+v_p(n)$$ for any odd prime $p$ and , $$\large v_2(x^n-y^n)=v_2(x-y)+v_2(x+y)+v_2(n)-1$$ If $n$ is odd then replacing $y$ by $-y$ we obtain $$ \large v_p(x^n+y^n)=v_p(x+y)+v_p(n)$$

The original problem: It is easy to see that $n=3$ satisfies the solution. We will prove that this the only solution.

Suppose for the sake of contradiction that $p \geqslant 5$ is a prime divisor of $n$. The original problem reduces to finding $n$ such that $$\large v_p(n^2) \leqslant v_p(2^n+1)$$ Observe that $n$ is odd and since $v_p(x^n+y^n)=v_p(x+y)+v_p(n)$, for odd $n$, $$\large v_p(2^n+1)=v_p(2+1)+v_p(n)$$

Since by our assumption $p \geqslant 5$ therefore $v_p(1+2)=v_p(3)=0$. And hence $$\large v_p(2^n+1)=v_p(n)$$ But this implies $$\large v_p(n^2) > v_p(n)$$ which is absurd. Therefore the only solution is $n=3$.

Is my solution valid? I'm quite new to lifting the exponent lemma. I read it in Evan Chen's handout titled 'Orders Modulo a Prime' and was pretty fascinated at the fact that it could be used to solve at least easy-moderate Olympiad problems. Please verify and see if I missed out something obvious. Also, I have not included a proof of the lemma as I think it would be pretty useless here :) Thank you.

  • $\begingroup$ Did you see this post, too? $\endgroup$ – Dietrich Burde Feb 27 '18 at 16:37
  • $\begingroup$ @DietrichBurde no I didn't, but doesn't that post ask for integers $n$ that divide $2^n+1$? I mean, my question is a bit different. $\endgroup$ – alphasquared Feb 27 '18 at 16:40
  • 1
    $\begingroup$ Don’t forget $n=1$… $\endgroup$ – Nemo Feb 27 '18 at 18:52
  • 2
    $\begingroup$ It seems like you're missing one of the critical features of the lifting the exponent lemma: $v_p(a^n+b^n)=v_p(a+b)+v_p(n)$ requires $p\mid(a+b)$. In this case, with $a=2$ and $b=1$, that means $p\mid 3$. So any argument based on higher $p$ can't be correct. $\endgroup$ – Steven Stadnicki Feb 27 '18 at 19:25
  • 1
    $\begingroup$ I certainly don't see a quick way to repair it, I'm afraid. $\endgroup$ – Steven Stadnicki Feb 27 '18 at 19:27

You were on the right track but, as you acknowledged in the question comments, you can't use $p \ge 5$ in your case with the Lifting The Exponent Lemma (LTE) since $p \not\mid 1 + 2 = 3$. Instead, first note

$$n^2 \mid 2^n + 1 \tag{1}\label{eq1}$$

obviously requires $n \mid 2^n + 1$.

As stated by S.C.B. in answer to MSE's When does $n$ divide $2^n+1$?, all values of $n \gt 1$ have a factor of $3$. Also, Primitive elements of the sequence of integers n such that n divides 2^n + 1 says

Every element of this sequence apart from 1 and 3 is divisible either by 27 or by 171.

Note that $27 = 3^3$ and $171 = 3^2\left(19\right)$. In particular, this means that each such primitive element has at least $2$ factors of $3$. In addition, Numbers n such that n divides 2^n + 1 states that, apart from the primitive elements, all other elements are generated among themselves by one of $3$ methods, i.e., multiplication of two elements, multiple of an element having the same prime factors as the element, and the lowest common multiple of two elements. In particular, this shows that all $n$ other than $1$ and $3$ have at least $2$ factors of $3$.

Since $n$ is odd, $3 \not\mid 1$, $3 \not\mid 2$ but $3 \mid 1 + 2 = 3$, the LTE can be used to determine limits on the power of $3$ in $n$. Using $p = 3$,

$$v_3\left(2^n + 1\right)= v_3(2 + 1) + v_3(n) = 1 + v_3(n) \tag{2}\label{eq2}$$

For \eqref{eq1} to hold requires

$$v_3\left(2^n + 1\right) \ge 2v_3(n) \tag{3}\label{eq3}$$

As such,

$$1 + v_3(n) \ge 2v_3(n) \; \; \Rightarrow \; \; 1 \ge v_3(n) \tag{4}\label{eq4}$$

Since \eqref{eq4} shows $n$ can have only up to $1$ factor of $3$, but all values $\gt 3$ have at least $2$ factors of $3$, this proves that $n = 1$ and $n = 3$ are the only solutions to \eqref{eq1}.


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.