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

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.

• Did you see this post, too? – Dietrich Burde Feb 27 '18 at 16:37
• @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. – alphasquared Feb 27 '18 at 16:40
• Don’t forget $n=1$… – Nemo Feb 27 '18 at 18:52
• 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. – Steven Stadnicki Feb 27 '18 at 19:25
• I certainly don't see a quick way to repair it, I'm afraid. – 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}.