Note 1
Miscellaneous Goodies

This note discusses some of the miscellaneous Number Theory topics that are not necessarily the major part in olympiad NT, but would be very useful when solving problems. At least for KMO, I am aware that it is generally required to prove many of the contents here during the write-ups, but some problems are virtually impossible to solve without previous knowledge on these topics!

1.1 \(p\)-adic Valuation &LTE Lemma

LTE Lemma, which stands for Lifting the Exponent Lemma, concerns about \(p\)-adic valuation of two integers. Before we get into the lemma, let’s discuss about \(p\)-adic valuation. If you prefer video over text, here is also a video explanation!

Definition 1.1.1

The \(\mathbf {p}\)-adic valuation of an integer \(n\) and prime \(p\), denoted as \(\nu _p (n)\), is the largest possible integer \(a\) such that \(p^a \mid n\).

Some examples could be \(\nu _2 (48) = 3\) and \(\nu _3 (54) = 3\). It is worth noting that some sources write this as \(V_p (n)\), so they most likely refer to the same thing.

Considering this notation as a function, we can notice that the following equation holds for all positive integers \(m, n\) and some prime \(p\). \[ \nu _p (mn) = \nu _p (m) + \nu _p (n) \] This is pretty self evident because it simply counts the number of \(p\) in \(m\) and \(n\). Another very interesting property is obtained when we add \(m\) and \(n\) instead of multiplying them. \[ \nu _p (m + n) \geq \min (\nu _p(m), \nu _p(n)) \] This could be pretty hard to see at first, but we can see it instantly if we factorize \(m\) and \(n\). Say \(m = p^x a\) and \(n = p^y b\) where \((p, a) = 1\) and \((p, b) = 1\). Without loss of generality, assume that \(x \geq y\). Then, \(m + n = p^y (p^{x-y} a + b)\) and the inequality holds. To see when the equality holds, we simply just have to make \(p^{x-y} a + b\) not divisible by \(p\). In other words, as long as \(x \neq y\), the equality holds.

This conclusion can lead to a more clean form. Given \(m\) and \(n\) such that \(\nu _p (m) < \nu _p (n)\), the following equation holds. \[ \nu _p (m + n) = \nu _p (m) \] I think this is pretty self-evident continuing from our conclusion.

Another very famous example would be Legendre’s formula, which states the following equation for positive \(n\) and prime \(p\). \[ \nu _p (n!) = \sum _{k=1}^\infty \left \lfloor \frac {n}{p^k} \right \rfloor \]

This is actually the same as the classic competition style problems that asks you the number of \(p\) in \(n!\). I will skip the proof because I think it is pretty self-evident.

Another very famous application is understanding why \(\binom {n}{r}\) is an integer. Obviously combinatoric-wise, its definition makes it an integer, but algebraic-wise, it is pretty interesting considering the fact that \(\binom {n}{r} = \frac {n!}{r! (n-r)!}\). To show this, it suffices to prove the following inequality for any prime \(p\). \[ \nu _p (n!) \geq \nu _p (r!) + \nu _p ((n-r)!) \] By Legendre’s formula, the inequality converts as \[ \sum _{k=1}^\infty \left \lfloor \frac {n}{p^k} \right \rfloor \geq \sum _{k=1}^\infty \left ( \left \lfloor \frac {r}{p^k} \right \rfloor + \left \lfloor \frac {n-r}{p^k} \right \rfloor \right ) \] and this is true because \(\lfloor a + b \rfloor \geq \lfloor a \rfloor + \lfloor b \rfloor \). With this notation and concept in mind, lets get into LTE Lemma!

Theorem 1.1.2: Lifting the Exponent Lemma

Let \(p\) be a prime number and \(x, y\) be integers such that \(p \mid x - y\), \(p \nmid x\), and \(p \nmid y\). Then, the respective equations hold for the three cases.

I.
\(\mathbf {p > 2}\) \[ \nu _p (x^n - y^n) = \nu _p (x - y) + \nu _p (n) \]
II.
\(\mathbf {p = 2}\) and \(\mathbf {2 \mid n}\) \[ \nu _2 (x^n - y^n) = \nu _2 (x^2 - y^2) + \nu _2 (n) - 1 \]
III.
\(\mathbf {p = 2}\) and \(\mathbf {2 \nmid n}\) \[ \nu _2 (x^n - y^n) = \nu _2 (x - y) \]

Before we prove this, an interesting extension that we can notice for odd \(n\) and \(p > 2\) is that \(\nu _p (x^n + y^n) = \nu _p (x + y) + \nu _p (n)\). This can be obtained by substituting \(-y\) for \(y\).

Proof.

To prove the lemma, first separate \(p\) into two cases where \(p > 2\) and \(p = 2\). The first case \(p > 2\) can be proven with induction.

First, consider the case when \(\nu _p (n) = 0\). Notice that because \(x - y \equiv 0 \pmod {p}\), \(x \equiv y \pmod {p}\). Moreover, \[ x^n - y^n = (x - y) \left ( \sum _{k=1}^n x^{n-k} y^{k-1} \right ) \] holds and \(\sum _{k=1}^n x^{n-k} y^{k-1} \equiv \sum _{k=1}^n x^{n-1} \not \equiv 0 \pmod {p}\). In other words, \(\nu _p (x^n - y^n) = \nu _p (x - y) + \nu _p (n)\).

Similarly, consider the base case when \(\nu _p (n) = 1\). Let \(n = kp\) where \(p \nmid k\) and consider the following equations. \[ x^{kp} - y^{kp} = \left ( x^p - y^p \right ) \left ( \sum _{i=1}^k x^{pk - ip} y^{ip - p} \right ) \] Notice that because \[ \sum _{i=1}^k x^{pk - ip} y^{ip - p} \equiv \sum _{i=1}^k x^{pk - p} \equiv k x^{pk - p} \not \equiv 0 \pmod {p} \] holds, \(\nu _p (x^n - y^n) = \nu _p (x^p - y^p)\). Continuing, \[ x^p - y^p = (x - y) \left ( \sum _{k=1}^p x^{p-k} y^{k-1} \right ) \] and \(\sum _{k=1}^p x^{p-k} y^{k-1} \equiv p x^{p-1} \equiv 0 \pmod {p}\). Substituting \(y = x + pt\) to the expression constructed by definition, \[ x^{p-k} y^{k-1} = x^{p-k} (x + pt)^{k-1} + x^{p-k} \left ( x^{k-1} + (k-1) x^{k-2} pt + \alpha \right ) \] where \(p^2 \mid \alpha \). Therefore, the following congruences hold. \begin{align*} \sum _{k=1}^p x^{p-k} y^{k-1} &\equiv \sum _{k=1}^p x^{p-k} x^{k-1} + x^{p-k} (k-1) x^{k-2} pt \\ &\equiv \sum _{k=1}^p x^{p-1} + x^{p-2} (k-1) pt \\ &\equiv p x^{p-1} + \frac {p(p-1)}{2} x^{p-2} pt \equiv p x^{p-1} \\ &\not \equiv 0 \pmod {p^2} \end{align*}

In other words, \(\nu _p (x^p - y^p) = \nu _p (x - y) + 1 = \nu _p (x - y) + \nu _p (n)\) and the base case holds.

Continuing, it suffices to show that if the equation holds for \(\nu _p (n) = a\), then it also holds for \(\nu _p (n) = a + 1\). Let \(n = p^a b\) where \(p \nmid b\), and consider the following equations. \begin{align*} \nu _p \left ( x^{p^{a+1} b} + y^{p^{a+1} b} \right ) &= \nu _p \left ( \left ( x^{pb} \right )^{p^a} + \left ( y^{pb} \right )^{p^a} \right ) \\ &= \nu _p \left ( x^{pb} - y^{pb} \right ) + a \\ &= \nu _p (x - y) + \nu _p (pb) + a = \nu _p (x - y) + a + 1 \\ &= \nu _p (x - y) + \nu _p (n) \end{align*}

Therefore by induction, the first case holds.

To prove the second case, consider the following equations with \(n = 2^a b\) where \(2 \nmid b\). \begin{align*} \nu _2 \left ( x^n - y^n \right ) &= \nu _2 \left ( \left ( x^{2^a} \right )^b - \left ( y^{2^a} \right )^b \right ) \\ &= \nu _2 \left ( \left ( x^{2^a} - y^{2^a} \right ) \left ( \sum _{k=1}^b \left ( x^{2^a} \right )^{b-k} \left ( y^{2^a} \right )^{k-1} \right ) \right ) \\ &= \nu _2 \left ( x^{2^a} - y^{2^a} \right ) \end{align*}

Moreover, because \begin{align*} x^{2^a} - y^{2^a} &= \prod _{k=1}^a \left ( x^{2^{a-k}} + y^{2^{a-k}} \right ) \cdot (x - y) \\ &= \prod _{k=1}^{a-1} \left ( x^{2^{a-k}} + y^{2^{a-k}} \right ) \cdot (x + y) (x - y) \end{align*}

holds and \(x^{2^k} + y^{2^k} \equiv 2 \pmod {4}\) for \(k > 1\), it is evident that \[ \nu _p \left ( x^{2^a} - y^{2^a} \right ) = \nu _p (x - y) + \nu _p (x + y) + a - 1 \] holds and the second case holds.

Finally, the last case can be simply proven with the following equation. \[ x^n - y^n = (x - y) \left ( \sum _{k=1}^n x^{n-k} y^{k-1} \right ) \] Notice that because \(\sum _{k=1}^n x^{n-k} y^{k-1} \equiv \sum _{k=1}^n x^{n-1} \equiv n x^{n-1} \not \equiv 0 \pmod {p}\), \(\nu _2 (x^n - y^n) = \nu _2 (x - y)\).

This proof was quite long, but absolutely worth it! Before we move on to a more advanced usage, here is a simple example. \[ \nu _3 \left ( 4^3 + 5^3 \right ) = \nu _3 \left ( 4^3 - (-5)^3 \right ) = \nu _3 (4 + 5) + \nu _3 (3) = 2 + 1 = 3 \] To check this, notice that \(\nu _3 (4^3 + 5^3) = \nu _3 (64 + 125) = \nu _3 (189) = 3\). Continuing, here is another problem.

Exercise 1.1.3: Enoch’s Problem

Find the greatest integer \(a\) such that \(2^a \mid 7^{2026} - 1\).

Solution.

Note that it suffices to find \(v_2 (7^{2026} - 1)\). Using LTE, we can see that \(v_2 (7^2 - 1) + v_2 (2026) - 1 = 4 + 1 - 1 = 4\). Therefore, the greatest integer \(a\) is \(4\).

With this idea in mind, let’s take a look at how LTE can be used to solve a more complicated problem.

Exercise 1.1.4

For all positive integers \(k\), show that \(2\) is a primitive root modulo \(5^k\).

Solution.

First, recall that \(2\) is a primitive root mod \(5^k\) if \(\min (2) = \phi (5^k)\) for \(2^n \equiv 1 \pmod {5^k}\). Notice that for \(2^n\) to be congruent to \(1\) mod \(5\), \(n\) must be a multiple of \(4\) since cycles \(2, -1, -2, 1\). Therefore, let \(n = 4N\).

Rewriting the congruence, \(16^N - 1 \equiv 0 \pmod {5^k}\) and the following inequality holds. \[ \nu _5 \left ( 16^N - 1 \right ) = \nu _5 \left ( a \cdot 5^k \right ) \geq k \] Using LTE, it is evident that \(\nu _5 \left ( 16^N - 1 \right ) = \nu _5 (16 - 1) + \nu _5 (N) \geq k\) and \(\nu _5 (N) \geq k - 1\). Therefore, \(N \geq 5^{k-1}\) and \(n \geq 4 \cdot 5^{k-1} = \phi (5^k)\) holds and \(2\) is a primitive root mod \(5^k\).

This is much simpler than induction, and is it for this section! I think LTE is one of those very powerful technique that often breaks the problem just by applying it. In the next section, we will discuss about combinatoric approach to NT problems.