Difference between revisions of "Lifting the Exponent Lemma"

Revision as of 21:10, 3 February 2022

Lifting the exponent allows one to calculate the highest power of an integer that divides various numbers given certain information. It is extremely powerful and can sometimes "blow up" otherwise challenging problems.

Let $p$ refer to an odd prime. We can split up LTE into six identities (where $\nu_p(Z)$ represents the largest factor of $p$ that divides $Z$ ):

From (http://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvYy82LzdjNTI1OGIyMmNjYmZkZGY4MDhhY2ViZTc3MGE1NDRmMzFhMTEzLnBkZg==&rn=TGlmdGluZyBUaGUgRXhwb25lbnQgTGVtbWEgLSBBbWlyIEhvc3NlaW4gUGFydmFyZGkgLSBWZXJzaW9uIDMucGRm):

$\nu_p(x^n-y^n)=\nu_p(x-y)+\nu_p(n)$ , if $p|x-y$ .

$\nu_2(x^n-y^n)=\nu_2(x-y)+\nu_2(n),$ if $4|x-y$ .

$\nu_2(x^n-y^n)=\nu_2(x-y)+\nu_2(x+y)+\nu_2(n)-1$ , if $2|x-y$ .

$\nu_p(x^n+y^n)=\nu_p(x+y)+\nu_p(n)$ , if $p|x+y$ .

From (https://arxiv.org/abs/1810.11456):

$\nu_2(x^n+y^n)=1$ , if $2|x+y$ and $n$ is even.

$\nu_2(x^n+y^n)=\nu(x+y)$ if $2|x+y$ and $n$ is odd.

@@ Line 5: / Line 5: @@
 From (http://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvYy82LzdjNTI1OGIyMmNjYmZkZGY4MDhhY2ViZTc3MGE1NDRmMzFhMTEzLnBkZg==&rn=TGlmdGluZyBUaGUgRXhwb25lbnQgTGVtbWEgLSBBbWlyIEhvc3NlaW4gUGFydmFyZGkgLSBWZXJzaW9uIDMucGRm):
-<math>\nu_p(x^n-y^n)=\nu_p(x+y)+\nu_p(n)</math>, if <math>p|x+y</math>.
+<math>\nu_p(x^n-y^n)=\nu_p(x-y)+\nu_p(n)</math>, if <math>p|x-y</math>.
 <math>\nu_2(x^n-y^n)=\nu_2(x-y)+\nu_2(n),</math> if <math>4|x-y</math>.

Page

Toolbox

Search

Difference between revisions of "Lifting the Exponent Lemma"

Revision as of 21:10, 3 February 2022