Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 ExponentLift

Source Notebook

Compute the p-adic valuation for certain integers using the lifting-the-exponent lemma

Contributed by: Shenghui Yang

ResourceFunction["ExponentLift"][x,y,n,p]

computes the p-adic integer exponent of xn±yn using the lifting-the-exponent (LTE) lemma for some x and y.

Details

A unique value α=vp(x) is defined as the valuation of an integer x if pα divides x and pα+1 does not divide x.
vp(0)=∞ for all primes p.
The lifting-the-exponent (LTE) lemma significantly simplifies the computation of p-adic valuation of xn±yn by applying the number theoretic property of binomial coefficients mod any odd prime.
LTE significantly simplifies the computation of 2-adic valuation of xn±yn because of x2k+y2k≡1(mod4) for any odd x and y.
The p-adic LTE requires that neither x nor y is a multiple of prime p and that p divides at least one of x-y or x+y.
ResourceFunction["ExponentLift"] in general returns an Association to indicate the feasible p-adic valuation by LTE for xn+yn OR xn-yn.
ResourceFunction["ExponentLift"] returns an association to indicate the 2-adic valuation by LTE for xn+yn AND xn-yn iff x,y and n are odd and 4 divides x-y.
ExponentLift returns Missing["NotApplied"] for both "Sum" and "Difference" field if the input fails to meet the requirements of LTE.

Examples

Basic Examples (2) 

Find the 7-adic valuation of n=10199+4199:

In[1]:=
res = ResourceFunction["ExponentLift"][10, 4, 199, 7]
Out[1]=

Therefore 7 divides n but no other power of 7 does:

In[2]:=
With[{input = 10^199 + 4^199}, {res["Sum"], IntegerExponent[input, 7], Mod[input, 7] == 0, Mod[input, 7^2] == 0} ]
Out[2]=

Find the 17-adic valuation of n=19867-2867:

In[3]:=
res = ResourceFunction["ExponentLift"][19, 2, 867, 17]
Out[3]=

Therefore 173 divides n and no higher power of 17 does:

In[4]:=
With[{input = 19^867 - 2^867}, {res["Difference"], IntegerExponent[input, 17], Mod[input, 17^3] == 0, Mod[input, 17^4] == 0} ]
Out[4]=

Scope (2) 

LTE can handle extremely large numbers without computing the exponential form:

In[5]:=
res = ResourceFunction["ExponentLift"][19, 2, 5*17^10, 17]
Out[5]=

Use PowerMod to verify 195×1710- 25×1710 is a multiple of 1711 but not of 1712 or higher power:

In[6]:=
PowerMod[19, 5*17^10, 17^11] - PowerMod[2, 5*17^10, 17^11]
Out[6]=
In[7]:=
PowerMod[19, 5*17^10, 17^12] - PowerMod[2, 5*17^10, 17^12]
Out[7]=

Properties and Relations (1) 

The only case when "Difference" and "Sum" fields are both integral is when p=2, 4 divides x-y and x, y and n are all odd numbers:

In[8]:=
ResourceFunction["ExponentLift"][123, 75, 199, 2]
Out[8]=
In[9]:=
{IntegerExponent[123^199 - 75^199, 2], IntegerExponent[123^199 + 75^199, 2]}
Out[9]=

Possible Issues (2) 

LTE requires that the base of two exponentials are coprime to the prime p:

In[10]:=
ResourceFunction["ExponentLift"][7, 14, 99, 7]
Out[10]=
In[11]:=
{IntegerExponent[7^99 - 14^99, 7], 99 + ResourceFunction["ExponentLift"][1, 8, 33, 7]["Difference"]}
Out[11]=

LTE also requires that the prime p divides either the difference or the sum of the first two arguments:

In[12]:=
ResourceFunction["ExponentLift"][7, 8, 99, 11]
Out[12]=

The following works because 7-18 ≡ -11 ≡ 0 (mod 11):

In[13]:=
ResourceFunction["ExponentLift"][7, 18, 99, 11]
Out[13]=

Neat Examples (6) 

Find the least n such that 123n-99n is a multiple of 10920. No brute force method is available to find the solution in the life time of the universe. First let's confirm that 109 is a prime and its coprime relations:

In[14]:=
{PrimeQ[109], CoprimeQ[123, 109], CoprimeQ[99, 109]}
Out[14]=

However, direct usage of LTE is not valid because 123-99 is not a multiple of 109:

In[15]:=
{ResourceFunction["ExponentLift"][123, 99, 2, 109], Divisible[123 - 99, 109]}
Out[15]=

Instead, one finds the least value of k such that 123k-99k is a multiple of 109:

In[16]:=
count = 0; res = With[{pp = 109}, ResourceFunction["TableWhile"][ count = k; Mod[PowerMod[123, k, pp] - PowerMod[99, k, pp], pp], {k, (Mod[#, pp] != 0) &}]]; {count, res}
Out[18]=

This means that 109 divides 1236 - 996 and LTE is applicable in this new form 123n-99n=(1236)m-(996)m:

In[19]:=
ResourceFunction["ExponentLift"][123^6, 99^6, 1, 109]
Out[19]=

Therefore the least n=6m is found with least m such that v109((1236)m-(996)m)=19:

In[20]:=
ResourceFunction["ExponentLift"][123^6, 99^6, 109^19, 109]
Out[20]=

n=6×10919 is the least value such that 10920 divides 123n-99n:

In[21]:=
PowerMod[123, 6*109^19, 109^20] - PowerMod[99, 6*109^19, 109^20]
Out[21]=

Publisher

Shenghui Yang

Requirements

Wolfram Language 13.0 (December 2021) or above

Version History

  • 1.0.0 – 17 January 2024

Source Metadata

Related Resources

License Information