Lifting the Exponent (LTE)

Lifting the Exponent (LTE) is a powerful tool in number theory. Before we get started, let's make sure we know a bit of notation:

Definition: $\nu_p (x)$ denotes the largest nonnegative integer $k$ such that $p^k \mid x$, where $x$ is a nonzero integer. In other words, $p^k|x$ but $p^{k+1}\nmid x$. Sometimes we also denote this by $p^k||x$, or say $p^k$ mostly divides $x$.

Now, we can get started!

The idea is that $\nu_p (a^2-b^2) = \nu_p ((a-b)(a+b)) = \nu_p (a-b) + \nu_p (a+b)$.

Now, I'll introduce LTE:

LTE for odd primes (first form): Let $p>2$ be a prime and let $a,b$ be integers with $p \not \mid ab$ and $p \mid a-b$. Then

$$\nu_p (a^n-b^n) = \nu_p (a-b)+ \nu_p (n).$$

We care about this result because it lets us reduce powers very quickly!

Proof. We induct on $\nu_p (n)$.

Base case: $\nu_p (n)=0$.

Then $p \not \mid n$, and we have $$v_p (a^n-b^n) = \nu_p (a-b) + \nu_p (a^{n-1}+a^{n-2}b+ \dots +b^{n-1} ),$$ and we want to show this equals $\nu_p (a-b)$.

Indeed, since $p \mid a-b$, we have $a \equiv b$ mod $p$, and so $$a^{n-1} + a^{n-2} b + \dots + b^{n-1} \equiv n a^{n-1} \pmod p.$$ Since neither $n$ nor $a$ is divisible by $p$, this last quantity is not divisible by $p$, so we are done with the base case.

However, we need a second base case (you'll see why later).

Base case 2: $\nu_p (n)=1$.

Write $a = m+b$. The trick is to re-write $a^n - b^n$. We have $$\nu_p (a^n-b^n) =\nu_p\left((m+b)^n - b^n\right) = \nu_p \left(\left( \displaystyle\sum_{i=0}^n m^ib^{n-i} \binom{n}{i} \right) -b^n \right) = \nu_p \left( \displaystyle\sum_{i=1}^n m^ib^{n-i} \binom{n}{i} \right)$$ by the Binomial Theorem.

Now note $p \mid a-b \implies p \mid m$, so for all $i>2$, we know that the largest power of $p$ dividing $m^i b^{n-i} \binom{n}{i}$ has an exponent of $\nu_p(m) + 2$. Let's call this $z$.

Now, consider when $i=1,2$: We get the terms

$m b^{n-1} n + m^2 b^{n-2} \dfrac{n(n-1)}{2}$.

Since $p \mid n$ but $p^2 \not \mid n$, we have that $p^z$ divides the second term, and $p^{z-1}$ divides the first term, and $p^z$ does not divide the first term.

Thus, putting everything together,

$\nu_p (a^n-b^n) = \nu_p (p^{z-1} \cdot blah + p^z \cdot more blah)$, where $p \not \mid blah$, so the valuation is $\nu_p(a^n-b^n)=z-1 = \nu_p(m) + 1$ as desired.

Inductive step: Proving the result for $\nu_p (n)=k+1$ given $\nu_p (n)=k$.

This is an easy example of induction:

Write $n = px$. Then by our inductive hypothesis, $$\begin{align*} \nu_p (a^n-b^n) &= \nu_p (a^{px} - b^{px} ) \\\ &= \nu_p ( (a^p)^x - (b^p)^x) \\\ &= \nu_p (a^p-b^p) + \nu_p (x), \end{align*}$$ since $\nu_p (x) = k$.

Now $\nu_p (a^p-b^p) = \nu_p (a-b) + 1$, so the end result is $k+1$ as desired.

Clearly, if we change $b$ to $-b$ in the first form of the theorem, we are done. There is just one small point here: $n$ should be odd so that we can factorize $a^n+b^n$. The rest of the proof is just the same.

Now, what happens if $p=2$?

LTE for $p=2$: If $x,y$ are odd integers and $n$ is even, then $$\nu_2 (x^n-y^n) = \nu_2 (x^2-y^2) + \nu_2 (n)-1.$$ The proof is very similar, with induction again. I'll leave it as an exercise to the reader.

Now, let's see LTE at work!

First, a short trick:

First, there's an annoying case when $n$ is even: Since $p \mid x+1$, then $x \equiv -1 \mod p$ and thus $x^n \equiv 1 \mod p$. It follows that $x^n + 1 \equiv 2 \mod p$, and thus $\nu_p (x^n+1)=0$.

Now, if $n$ is odd, $\nu_p (x^n + 1) = \nu_p ( x^n - (-1)^n ) = \nu_p (x+1) + \nu_p (n)$ by LTE!

LTE for odd primes (second form). Let $p>2$ be a prime and let $a,b$ be integers with $p \not \mid ab$ and $p \mid a+b$. Also, suppose that $n$ is a positive integer. Then $$\nu_p (a^n+b^n) = \nu_p (a+b)+ \nu_p (n).$$

We want to use LTE to evaluate $\nu_2 (3^n-1^n)$. However, if you go back to the statement of LTE, we require $n$ to be even.

Luckily, this is an easy fix- if $n$ is odd and $n\ge 1$ then $3^n \not \equiv 1$ mod $4$, so we obtain an easy contradiction.

Now, if $n$ is even then $\nu_2 (3^n-1^n) = 2 + \nu_2 (n)$.

Meanwhile, $2^n | 3^n-1$ shows $\nu_2 (3^n-1) \ge n$.

Thus $2+\nu_2 (n) \ge n$, and $n$ is even, so easy bounding tells us $n=2,4$.

Once again, our solutions are $n=1,2,4$.

This problem is trickier than the previous one, so I'll just give the solution. However, it has lots of interesting ideas which the reader should be able to understand and the inequality isn't too strong...:

Take any $p|b$, so that $p>2$ since $b$ is odd. Then $v_p (a^n-1) \ge n$.

Now notice $a^n-1 | (a^n)^{p-1} - 1 = (a^{p-1} )^n - (1^{p-1})^n$.

Thus, since $p|a^{p-1}-1$ by Fermat, we have

$\nu_p ((a^{p-1})^n - 1 ) = \nu_p (a^{p-1} - 1) + \nu_p (n)\ge \nu_p (a^n-1) \ge n$.

But this clearly implies

$a^b > a^{p-1} -1 \ge p^{\nu_p (a^{p-1} - 1)} \ge \dfrac{p^n}{n} \ge \dfrac{3^n}{n}$, which gives us the desired inequality.

Now, I'll leave the reader with one more exercise to do, another inequality:

(More Romanian TST) Let $m\geq 2$ be an integer. A positive integer $n$ has the property that for any positive integer $a$ coprime with $n$, we have $a^m - 1\equiv 0 \pmod n$.

Prove that $n \leq 4m(2^m-1)$.

By Fermat, $a\equiv a^p\equiv 1\mod p$, so $\nu_p(a-1)=\nu_p(a^p-1)-1\ge n-1$.

If $1+k$ is not a power of $2$, choose an odd prime $p|1+k$ and take $n=p^m$. Then, for each $j$ not divisible by $p$, we have $\nu_p(j^n+(k+1-j)^n)=\nu_p(k+1)+\nu_p(n)\ge m+1$. Also, if $p|j$ (and, thereby, $p|k+1-j$), then $n|p^m|p^n|j^n$ so the sum in question is divisible by $p^m=n$. If $1+k$ is a power of $2$, then take an odd prime divisor $p$ of $k$ and repeat the above argument with $k-1$ instead of $k$ (the last term $k^n$ is, obviously, not a problem).

$k$ must be odd since the sum of $2$ squares is divisible by $3$ only if both squares are divisible by $3$. If $p|x+y$, then $p$ is odd and $\nu_p(3^n)=\nu_p(x^k+y^k)=\nu_p(k)+\nu_p(x+y)$, which means that $p=3$, so $x+y=3^m$ and $n=\nu_3(k)+m$. Now it is just cases.

a) $m>1$. Then $\nu_3(k)\le k-2$ for all $k>1$, and $M=\max(x,y)\ge 5$ so $$x^k+y^k\ge M^k> \frac 12 3^m 5^{k-1}> 3^m5^{k-2}\ge 3^{m+k-2}\ge 3^{m+\nu_3(k)}=3^n,$$ which gives an immediate contradiction.

b) $m=1$. Then $x=1,y=2$ (or vice versa) and we get $3^{1+\nu_3(k)}=1+2^k$, meaning $k\le 2(1+\nu_3(k))$ whence $\nu_3(k)=1$, so $n=2$ giving the only solution $3^2=1^3+2^3$.

$n$ must be $1$ or prime (otherwise any nontrivial divisor $d$ of $n$ will divide both $(n-1)!$ and $n^m$. Now, $n=2, m=1$ is a solution, $n=1$ is not, so it suffices to consider the case when $n$ is an odd prime. If $m$ is odd, then $\nu_2(n^m-1)=\nu_2(n-1)<\nu_2((n-1)!)$ if $n>3$. $n=3$ is not a solution, so we can consider only even $m$.

Then $\nu_2((n-1)!)=\nu_2(m)-1+\nu_2(n+1)+\nu_2(n-1)$ or $\nu_2((n-2)!)=\nu_2(n+1)+\nu_2(m)-1$. But the left hand side is at least $\frac{n-3}{2}$ (just count evens up to $n-2$), so $m\ge 2^{(n-1)/2}/(n+1)$, which is at least $n$ for $n\ge 18$. It remains to note that $n^n>(n-1)!+1$ for $n>1$.

Now comes the remaining finite trial and error part: $4!+1=5^2$ is good $6!+1=721$ is bad $n=11$ gives $\nu_2(m)=9$ which is far too large. $n=13$ gives $\nu_2(m)=10$, which is too large too $n=17$ gives some big $\nu_2(m)$ as well.

Applications of LTE

Lifting the Exponent Lemma explains what LTE is, and its proof. The motivation should be quite obvious, and now we will see some nice applications of this popular theorem. In fact, it can solve a good number of olympiad problems that appeared in different olympiads thoughout the world, including IMO. Let's start with an IMO problem. It's a really really great problem which involves many important ideas. While solving the problems, we will assume the readers has minimum familiarity with Divisibility

Problem (IMO $1990$, Problem $3$) Find all $n$ such that $n^2|2^n+1$.

When we encounter such problems, we usually try to find $n$ by finding some of its prime factors first. Because, it is kinda obvious, finding all such $n$ is tedious or impossible otherwise, if you work on the problem a bit.

Here is an idea crucial for many problems.

Take the smallest prime factor of $n$

Assume that, $p$ is the smallest prime factor of $n$. Then $p|2^n+1$ as well. And our advantage is that, we have Fermat's little theorem to provide with more information, $p|2^{p-1}-1$, since $2$ is even and $p$ is odd.

Now, certainly, $p|2^{2n}-1$ since $2^n+1|2^{2n}-1$. We know that, if $a^x\equiv b^x\pmod m$ and $a^y\equiv b^y\pmod m$, then $a^{\gcd(x,y)}\equiv b^{\gcd(x,y)}\pmod m$. Using this, we get $p|2^{\gcd(2n,p-1)}-1$. There is another crucial idea here.

Since $p$ is the smallest prime factor of $n$ and any prime factor of $p-1$ is less than or equal to $p-1$, any prime factor of $p-1$ would be co-prime to $n$

Therefore, $\gcd(2n,p-1)=\gcd(2,p-1)=2$, since $p$ is odd. This gives us, $p|2^2-1=3$. $p=1$ is impossible (which we should already discard considering $n>1$), so $p=3$. Now that we know a prime factor of $n$, we should try to find either another prime factor, or the exponent of that prime factor. Focusing on the power seems more legit. So, we assume $n=3^km$ where $3\nmid m$, which also means $\nu_3(n)=k$. Since $n^2|2^n+1$, $p^{2k}|2^n+1$ as well. This is where we are gonna need LTE! \begin{eqnarray*} \nu_3(2^n+1) & = & \nu_3(3)+\nu_3(n)\newline & = & k+1 \end{eqnarray*} But on the other hand, we must have $\nu_3(2^n+1)\geq2k$ or $k+1\geq2k$ or $k=1$. Now that $n=3m$, assume that the smallest prime factor of $m$ is $q$, which exists if $m>1$. In a similar fashion we just showed that $p=3$, show that $q=7$ using $q|2^{3m}+1=8^m+1$. But then we have $7|8^m+1$, whereas $8^m+1\equiv1+1\pmod2\pmod7$, so contradiction! Thus, no such $q$ exists and $m=1$.

We are done and $\boxed{n=3}$ is the only solution other than $1$.

For some positive integer $n$, the number $3^n-2^n$ is a perfect power of a prime. Prove that $n$ is a prime.

a) Let $x$ and $y$ be two positive real numbers such that for each positive integer $n$, the number $x^n-y^n$ is a positive integer. Show that $x$ and $y$ are both positive integers.

b) Let $x$ and $y$ be two positive rational numbers such that for infinitely many positive integers $n$, the number $x^n-y^n$ is a positive integer. Show that $x$ and $y$ are both positive integers.

Let $n$ be a square-free number. Show that there does not exist positive integers $x$ and $y$ such that $(x+y)^3 | x^n+y^n$.

(Balkan 1993). Let $p$ be a prime number and $m>1$ be a positive integer. Show that if for some positive integers $x>1, y>1$ we have $$\frac{x^p+y^p}{2}= \left( \frac{x+y}{2} \right)^m,$$ then $m=p$.

Confirm that, $3^{n+1}||2^{3^n}+1$, or $\nu_3(2^{3^n}+1)=n+1$. Note, this also means that there are infinite $n$ such that $n|2^n+1$.