Difference between revisions of "Lifting the Exponent Lemma"
(Finding the highest power of primes dividing certain numbers) |
|||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 5: | Line 5: | ||
From (http://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvYy82LzdjNTI1OGIyMmNjYmZkZGY4MDhhY2ViZTc3MGE1NDRmMzFhMTEzLnBkZg==&rn=TGlmdGluZyBUaGUgRXhwb25lbnQgTGVtbWEgLSBBbWlyIEhvc3NlaW4gUGFydmFyZGkgLSBWZXJzaW9uIDMucGRm): | From (http://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvYy82LzdjNTI1OGIyMmNjYmZkZGY4MDhhY2ViZTc3MGE1NDRmMzFhMTEzLnBkZg==&rn=TGlmdGluZyBUaGUgRXhwb25lbnQgTGVtbWEgLSBBbWlyIEhvc3NlaW4gUGFydmFyZGkgLSBWZXJzaW9uIDMucGRm): | ||
| − | <math>\nu_p(x^n-y^n)=\nu_p(x | + | <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>. | <math>\nu_2(x^n-y^n)=\nu_2(x-y)+\nu_2(n),</math> if <math>4|x-y</math>. | ||
| − | <math>\nu_2(x^n-y^n)=\nu_2(x-y)+\nu_2(x+y)+\nu_2(n)-1</math>, if <math>2|x-y</math>. | + | <math>\nu_2(x^n-y^n)=\nu_2(x-y)+\nu_2(x+y)+\nu_2(n)-1</math>, if <math>2|x-y</math> and <math>n</math> is even. |
| − | <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> and <math>n</math> is odd. |
From (https://arxiv.org/abs/1810.11456): | From (https://arxiv.org/abs/1810.11456): | ||
Latest revision as of 23:30, 30 April 2024
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 
refer to an odd prime. We can split up LTE into six identities (where 
represents the largest factor of that divides 
):
, if 
.
if 
.
, if 
and 
is even.
, if 
and is odd.
From (https://arxiv.org/abs/1810.11456):
, if 
and is even.
if and is odd.
