A solution using 'Lifting the exponent' lemma to IMO 1990 P3

Question

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.

Answer 1

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 use that

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

obviously requires $n \mid 2^n + 1$ (useful details about this are in When does $n$ divide $2^n+1$?).

Next, 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 $\gt 3$ 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. Generating any element using $3$ will result in a number with at least two factors of $3$. Also, note using any of the $3$ methods will not reduce the number of factors of $3$ in the generated element. Thus, this shows that all $n$ other than $1$ and $3$ must have at least $2$ factors of $3$.

Since $n$ is odd, $3 \not\mid 1$ and $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$,

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

For \eqref{eq1A} to hold requires

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

As such, \eqref{eq2A} shows that

$$1 + \nu_3(n) \ge 2\nu_3(n) \; \; \to \; \; 1 \ge \nu_3(n) \tag{4}\label{eq4A}$$

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

Answer 2

Based somewhat on Proof Verification: Find all positive integer $n$ for which $n^2|2^n+1.$, here is a simpler & more self-contained proof than in my other answer to determine the $n$ which satisfy

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

For $n \gt 1$, let $p$ be the smallest prime factor of $n$. Since $2^{n} \equiv -1 \pmod{p}$, then $2^{2n} \equiv 1 \pmod{p}$. This means the multiplicative order of $2$ modulo $p$ must divide $2n$, i.e., $\operatorname{ord}_{p}(2) = j \mid 2n$. Since $j \mid \varphi(p) = p - 1$ (i.e., Euler's totient function of $p$), this means $j \lt p$. Since $p$ is the smallest prime factor of $n$, then $\gcd(j, n) = 1$, so $j \mid 2$, i.e., $j = 2 \; \to \; p = 3$.

Since $n$ is odd, $3 \not\mid 1$ and $3 \not\mid 2$, but $3 \mid 1 + 2 = 3$, the Lifting-the-exponent lemma (LTE) can be used to get

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

For \eqref{eq1B} to hold requires

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

As such, \eqref{eq2B} shows that

$$1 + \nu_3(n) \ge 2\nu_3(n) \; \; \to \; \; 1 \ge \nu_3(n) \tag{4}\label{eq4B}$$

This means $\nu_3(n) = 1$, i.e., $n$ has exactly one factor of $3$. Thus, if $n \gt 3$, then $m = \frac{n}{3}$ must have other larger prime factors. Let $q$ be the smallest among them. This means $\operatorname{ord}_q(2) = k \mid 2(3)m$, and using basically the same argument as before, we get that $\gcd(k, m) = 1$, so $q \mid 2(3)$. Since $2^2 - 1 = 3$, $2^3 - 1 = 7$ and $2^6 - 1 = 3^2(7)$, this means $q = 7$.

However, $2^n$ is congruent to just $1$, $2$ or $4$ modulo $7$. Thus, $7 \not\mid 2^{n} + 1$. This contradiction proves there are no $n$ other than $1$ and $3$ which satisfy \eqref{eq1B}.