Skip to main content

Preliminaries of the LTE Lemma

In this post I will discuss the preliminary theory underlying the Lifting the Exponent Lemma (let's refer it to as LTE from now on) which is  one of the foundational topics of Olympiad Number Theory.  It is a useful technique to think of whenever we come across Diophantine equations having exponents and it is even better if those exponents are primes. Comfort with modular arithmetic is assumed. If the reader is not fluent in Modular arithmetic, a quick reading from any handout is sufficient. (I highly recommend  this )

So before starting things off, here are a few conventions that we will follow: We say an integer $b$ divides $a$ iff there is an integer $c$ such that $a = bc$. We denote it as $b \mid a$. We now take a look at more interesting things. 

Consider the following: What is the greatest power of $3$ that divides $63$? It is easy to see that it's $2$. i.e $3^2 \mid 63$. We denote this as $\nu_3(63) = 2$. So let us now define it formally. 

$\nu_p(x)$ is defined as the highest power in which a prime number $p$ divides $x$. So, if $\nu_p(x) = a$ then $p^a \mid x$ but $p^{a+1} \nmid x$. We also use the notation $$p^a || \; x$$ if and only if $\nu_p(x) = a$. From this we get the following relations(these are easy to prove if you understand the definition of $\nu_p(x)$ so I recommend you try to prove them on your own.) :   

  •  $\nu_p(xy) = \nu_p(x) + \nu_p(y)$ 
  •  $\nu_p(x+y) \ge \min\{\nu_p(x) , \nu_p(y)\}$ 
  •  $\nu_p(0) = \infty$ for all prime numbers $p$.  
  • If $p$ and $q$ are different prime numbers then the following holds true $$\nu_p(p^a q^b) = a$$  

We will now utilize the above properties and look at the following two lemmas.

Lemma: Let $x$ and $y$ be integers and let $n \in \mathbb{Z}^+$. For any arbitrary prime number $p$, such that $n$ and $p$ are coprime, $p \mid x-y$ and $p \nmid x$ and $p \nmid y$. We have the following $$\nu_p(x^n - y^n) = \nu_p(x-y)$$

Proof: We use the following well known algebraic trick $$x^n - y^n = (x-y)(x^{n-1}y^0 + x^{n-2}y + \dots + x^0y^{n-1})$$ Now we want to show $$p \nmid x^{n-1}y^0 + x^{n-2}y + \dots + x^0y^{n-1}$$ To show that this is actually true, we take advantage of the fact that $p \mid x-y$. Which implies that $x-y \equiv 0 \pmod{p}$. This gives the us following:   

$$x^{n-1} + x^{n-2}y + \dots + y^{n-1}$$$$\equiv x^{n-1} + x^{n-2} \cdot x + x^{n-3} \cdot x^2 + \dots + x \cdot x^{n-2} + x^{n-1}$$$$\equiv nx^{n-1}$$$$\not \equiv 0 \pmod{p}$$

Which concludes the proof. $\square$ 

Here's another important lemma. 

Lemma: Let $x$ and $y$ be integers and let $n$ be an odd positive integer. Given some arbitrary prime number $p$, such that $n$ and $p$ are co-prime, $p \mid x+y$, $p \nmid x$ and $p \nmid y$, the following holds true $$\nu_p(x^n + y^n) = \nu_p(x+y)$$  Proof: Since both $x$ and $y$ can take negative values, by the previous lemma we obtain $$\nu_p(x^n - (-y^n)) = \nu_p(x-(-y)) \implies \nu_p(x^n + y^n) = \nu_p(x+y)$$  Now observe that $n$ is odd and hence $(-y)^n$ can be replaced with $-y^n$ which finishes the proof. $\square$ 

We have now developed enough tools to take a look at the "LTE Lemma". Here it goes: 

Theorem: Let $x$ and $y$ be two integers. Let $n$ be a positive integer and let $p$ be an odd prime such that $p \mid x-y$ but $p \nmid x$ and $p \nmid y$. Then the following holds true $$\nu_p(x^n - y^n) = \nu_p(x-y) + \nu_p(n)$$

Proof: We will first prove that the following relation holds true $$\nu_p(x^p - y^p) = \nu_p(x-y) + 1$$

To prove this, we will prove two more claims, they are as follows $$p \mid x^{p-1} + x^{p-2}y + \dots + y^{p-1}$$

and  $$p^2 \nmid x^{p-1} + x^{p-2}y + \dots + xy^{p-2} + y^{p-1}$$ To prove the second sub-claim, just observe the fact that $$x^{p-1} + x^{p-2}y + \dots + xy^{p-2} + y^{p-1} \equiv px^{p-1} \equiv 0 \pmod{p}$$ Now denote by $d = x+kp$ where $k \in \mathbb{Z}$ For any integer $t \in [1 , p)$ we get:  

$$d^tx^{p-1-d} \equiv (x+kp)^{t} x^{p-1-t}$$ $$\equiv x^{p-1-t} \left(x^t + t(kp)(x^{t-1}) + \frac{t(t-1)}{2}(kp)^2(x^{t-2)} + \dots \right)$$$$\equiv x^{p-1-t} \left(x^t + t(kp)(x^{t-1}) \right)$$$$\equiv x^{p-1} + tkpx^{p-2} \pmod{p^2}$$ which gives us that $$d^{t}x^{p-1-t} \equiv x^{p-1} + tkpx^{p-2} \pmod{p^2}$$ where $t = \{1,2,3,4,\dots,p-1\}$ Using this we derive the following relations $$x^{p-1} + x^{p-2}y + \dots + xy^{p-2} + y^{p-1}$$ $$\equiv x^{p-1} + (x^{p-1} + kpx^{p-2}) + (x^{p-1} + 2kpx^{p-2}) + \dots + (x^{p-1} + (p-1)(kpx^{p-2})$$ $$\equiv px^{p-1} + (1+2+3+4+\dots+p-1)kpx^{p-2}$$ $$\equiv px^{p-1} + \left(\frac{p(p-1)}{2}\right) kpx^{p-2}$$$$\equiv px^{p-1} + \left(\frac{p-1}{2}\right) kp^2x^{p-1}$$$$\equiv px^{p-1} \not \equiv 0 \pmod{p^2}$$After successfully proving all our sub-claims, we can now move onto our main problem. We had to prove the following $$\nu_p(x^n - y^n) = \nu_p(x-y) + \nu_p(n)$$ The reader can hopefully now conclude the proof by themselves. The key to prove this is to convert $n$ in the form $p^{\omega}b$ where $p$ and $b$ are co-prime. $\square$ 

Theorem: Let $x$ and $y$ be integers and $n$ be an odd integer greater than zero and $p$ be an odd prime such that $p \mid x+y$ and neither $x$ nor $y$ is divisible by $p$. Then the following holds true $$\nu_p(x^n + y^n) = \nu_p(x+y) + \nu_p(n)$$ Proof:  Follows from the previous theorem $\square$ 

A careful reader must have observed that we have been imposing a weird condition on the primes, i.e we are always assuming that the primes are odd. Well, in part of the post, we'll look what exactly happens when the prime $= 2$.  

Theorem: Let $x$ and $y$ be two odd integers such that $4 \mid x-y$. Then the following holds $$\nu_2(x^n - y^n) = \nu_2(x-y) + \nu_2(n)$$Proof: We have previously proved that for any prime number $p$, which is co-prime to $n$ and $p \mid x-y$ and $p \nmid x,y$ then the following relation is true $$\nu_p(x^n - y^n) = \nu_p(x-y)$$ so it suffices to check that $$\nu_2 \left(x^{2^n} - y^{2^n}\right) = \nu_2(x-y) + n$$ which upon factorization leads to the following  

$$x^{2^n} - y^{2^n} = \left(x^{2^{n-1}} + y^{2^{n-1}} \right) \left( x^{2^{n-2}} + y^{2^{n-2}}\right) \dots \left(x^2 + y^2 \right)(x+y)(x-y)$$ Now since $$x \equiv y \equiv \pm 1 \pmod{4}$$ we see that the following is true for all positive integers $k$: $$x^{2^k} \equiv y^{2^k} \equiv 1 \pmod{4}$$ and so for $k \in \{1,2,3,4,\dots\}$ we have $$x^{2^k} + y^{2^k} \equiv 2 \pmod{4}$$ and using the fact that both $x$ and $y$ are odd and also since $4$ divides the difference of $x$ and $y$, $x + y \equiv 2 \pmod{4}$ which finishes the proof $\square$ 

Theorem: Let $x$ and $y$ be two odd positive integers and let $n$ be an even positive integer. Then $$\nu_2(x^n - y^n) = \nu_2(x-y) + \nu_2(x+y) + \nu_2(n) - 1$$

Proof: We will be using the fact that the square of an odd integer is of the form of $4k + 1$ for some integer $k$. Hence, for odd integers $x$ and $y$, we get that $4 \mid x^2 - y^2$. Now define $l$ to be an odd integer and $k$ be a positive integer such that $n  = l \cdot 2^{k}$. Then$$\nu_2(x^n - y^n) = \nu_2 \left(x^{l \cdot 2^k} - y^{l \cdot 2^k}\right)$$ $$= \nu_2 \left(\left(x^2 \right)^{2^{k-1}} - \left(y^2 \right)^{2^{k-1}}\right)$$$$\vdots$$ $$\nu_2(x-y) + \nu_2(x+y)+ \nu_2(n) - 1$$$\square$   

These were the fundamental theorems concerning the LTE lemma. I'm still in the process of collecting problems on the topic and hence I plan to write a second part of this where I'll discuss problems that use this lemma. 



Popular posts from this blog

Constructions in Number Theory

Hi, I am Emon, a ninth grader, an olympiad aspirant, hailing from Kolkata. I love to do olympiad maths and do some competitive programming in my leisure hours, though I take it seriously. I had written INOI this year. Today, I would be giving you a few ideas on how to Construct in Number Theory . Well, so we shall start from the basics and shall try to dig deeper into it with the help of some important and well-known theorems and perhaps, some fancy ones as well. Okay, so without further delay, let's start off... What do we mean by "Constructions"? If noticed, you can see that you often face with some problems in olympiad saying, "... Prove that there exists infinitely many numbers satisfying the given conditions" or "... Prove that there exists a number satisfying the above conditions." These are usually the construction-problems .  For example, let's consider a trivial example : Problem. Prove that there exist infinitely many integers $a$ such th

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The  European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved! To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul ! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal !  These solutions were actually found by Atul, Pranjal,  and Abhay  during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!! Okie Dokie, I think we should get started with the problems! Enjoy! Problem 1:  Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and

Q&A with experts about bashing

Heyy everyone! From the title, you can see that we are going to talk about  BASH.  Yesss, we are going to discuss whether you really need to learn bash or not?  Let me first introduce myself, I am Pranav Choudhary, a 10th grader from Haryana(India). I like to do geo and combo the most :PP. Oki so let's begin! For those of you who don't know what bashing is, lemme give you a brief introduction first. Bashing is basically a technique used to solve Geometry Problems. In general, when you try a geo problem you might think of angles, similarities, and some other techniques (e.g. Inversion, spiral similarity etc). All of which are called synthetic geometry. But sometimes people use various other techniques called "bash" to solve the same problems.  Now there are different kinds of bashing techniques, e.g. - Coordinate bash, Trig Bash, Complex bash, Barycentric Coordinates. Let me give you a brief introduction to each of them.  Coordinate Bash : You set one point as the orig