3
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$ – Gerry Myerson Aug 18 '14 at 12:57
  • $\begingroup$ 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 $\endgroup$ – Bart Michels Jun 3 '16 at 20:22
  • $\begingroup$ You can find or request more details at ProofWiki: proofwiki.org/wiki/Lifting_The_Exponent_Lemma_for_p%3D2 $\endgroup$ – Bart Michels Aug 24 '17 at 12:55
3
$\begingroup$

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.

$\endgroup$

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.