Lifting the exponent

I overheard mention of a particular problem on a recent British Mathematical Olympiad, namely the following:

A number written in base 10 is a string of 3^2013 digit 3s. No other digit appears. Find the highest power of 3 which divides this number.

Personally, I bemoan such problems that are trivialised by the knowledge of advanced theorems, as it enables competitors to gain an unfair advantage by rote-learning many results rather than demonstrating creative mathematical thought. In this case, the question is trivialised by a rather elegant but little-known lemma called lifting the exponent.

So, what does the lemma state? Firstly, we establish the following definition:

Definition: the p-adic valuation v_p(n) of an integer n to be the highest power of p which divides n. For example, v_2(40) = 3, since 2^3 divides 40 but 2^4 does not.

Then the lemma is as follows:

Theorem (lifting the exponent): Let p be an odd prime, and a and b integers such that neither a nor b is divisible by p, but p divides their difference ab. Then v_p(a^n − b^n) = v_p(ab) + v_p(n).

Why is this true? The idea is that we factorise a^n − b^n like so, where n = k p^m and k is not divisible by p:


The factors in the final factorisation are highlighted. It is clear that it is sufficient to prove that the yellow factor is coprime to p (which is easy, since all of the terms are congruent modulo p and are non-zero) and each of the blue factors are divisible by p (easy for the same reason) but not by p², as we shall prove:

  • If a and b are congruent modulo p², this is again trivial for the same reason as before.
  • Otherwise, we have to actually rely on the property that p is odd (if p = 2, we need a and b to be congruent modulo 4 rather than modulo 2). We let x and y be equal to a^p^i and b^p^i, respectively, for the obvious value of i, such that the factor is of the form:

Γ = x^(p-1) + x^(p-2) y + x^(p-3) y^2 + … + y^(p-1)

Then we set y = x + lp for some integer l (which we can do, since y and x are clearly congruent modulo p). Expand the factor Γ to produce a sum of binomial expansions; we can ignore all terms of order p² and higher since we’re only interested in the residue modulo p². This gives the following expression:

px^{p-1} + \frac{1}{2}p^2(p-1) x^{p-1}

The rightmost term vanishes, leaving something that is clearly not divisible by p². Consequently, the proof is complete and the result follows immediately.

Zsigmondy’s theorem

Another useful fact concerning a^n − b^n is this: except in a few exceptional cases, it has a new prime factor p that does not occur in any of ab, a² − b², a³ − b³, …, a^(n−1) − b^(n−1). The exceptions to the rule are the following:

  • a = 2, b = 1, n = 6: we have 2^6 − 1^6 = 63, whose prime factors are 3 and 7, which occur in 2^2 − 1^2 and 2^3 − 1^3, respectively.
  • a + b is a power of 2, and n = 2: then a² − b² = (a + b)(ab). The first factor is a power of 2 (so no new primes there), and the second factor is itself the previous term in the sequence (so, by definition, no new primes there either).

A related statement about Fibonacci numbers (where the integers a and b are replaced with irrational algebraic integers, and an extra factor of √5 slips in) is known as Carmichael’s theorem. Zsigmondy’s theorem and Carmichael’s theorem can be mutually generalised to other Lucas sequences.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s