Lifting the Exponent Lemma

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.

Page

Toolbox

Search

Lifting the Exponent Lemma