# lifting the exponent lemma for $p=2$.

I am trying to understand the proof of theorem 3 (in p.4) of http://www.artofproblemsolving.com/Resources/Papers/LTE.pdf

However, I dont understand the last sentence "This means the power of $2$ in all of the factors in the above product (except $x-y$) is one and we are done."

We have $x+y\equiv 2 \pmod{4}$. Hence $x^{2^n}-y^{2^n}\equiv 2^n(x-y) \pmod{4}$, but why this will imply the result we want? Pleas helps, thank you so much.

edit: It is equivalent to prove that $\sum_{k=0}^{n-1}v_2(x^{2^k}+y^{2^k})=n$.

• I think it would be better if this problem were self-contained (that is, if it had enough information so that I wouldn't have to go to another website to understand it). – Gerry Myerson Aug 18 '14 at 12:57
• The article is Amir Housein Parvardi, Lifting The Exponent Lemma (LTE), 2011. It can now be found e.g. here: taharut.org/imo/I5775/LTE.pdf – Bart Michels Jun 3 '16 at 20:22
• You can find or request more details at ProofWiki: proofwiki.org/wiki/Lifting_The_Exponent_Lemma_for_p%3D2 – Bart Michels Aug 24 '17 at 12:55

The point is that $x^{2^k}$ and $y^{2^k}$ are either both congruent to 1 or both congruent to -1 mod 4. Thus when you add them, you get something congruent to 2 mod 4, and if something is congruent to 2 mod 4, it has exactly one power of 2 in its prime factorization.