Elementary Number Theory in Mathematical Olympiads: From Modular Arithmetic to Lifting the Exponent

Number theory is one of the four standard pillars of mathematical olympiad competitions, alongside algebra, combinatorics, and geometry. Unlike calculus or analysis, elementary number theory focuses strictly on the properties of integers. Problems frequently have deceptively brief statements, yet solving them demands structural insight, careful modular reductions, and prime valuation techniques. This article presents the core theorems and practical tools needed to tackle contest problems, concluding with the Lifting the Exponent Lemma (LTE).

1. Divisibility and Prime Factorization

Given two integers $a$ and $b$ with $a \ne 0$, we say that $a$ divides $b$ (written $a \mid b$) if there exists an integer $k$ such that $b = k \cdot a$. When $a$ does not divide $b$, we write $a \nmid b$. Every integer divisibility argument rests on two classical results:

The second foundational result is the Fundamental Theorem of Arithmetic: every integer $n \ge 2$ can be written uniquely (up to the order of factors) as a product of prime numbers:

This canonical factorization introduces the $p$-adic valuation notation: for a prime $p$ and positive integer $n$, $v_p(n)$ denotes the exponent of the highest power of $p$ dividing $n$. In other words, $v_p(n) = \alpha$ if $p^\alpha \mid n$ and $p^{\alpha+1} \nmid n$. Valuations satisfy two practical rules: $v_p(ab) = v_p(a) + v_p(b)$, and $v_p(a + b) \ge \min(v_p(a), v_p(b))$, with equality whenever $v_p(a) \ne v_p(b)$.

2. Modular Arithmetic and Residue Systems

Modular arithmetic formalizes the arithmetic of remainders. We write $a \equiv b \pmod{m}$ if $m \mid (a - b)$. Congruence modulo $m$ defines an equivalence relation that respects addition, subtraction, and multiplication. If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then $a + c \equiv b + d \pmod{m}$ and $ac \equiv bd \pmod{m}$. However, division requires caution:

In particular, if $\gcd(c, m) = 1$, we can divide both sides of a congruence by $c$ without altering the modulus. When working with prime moduli, every non-zero residue has a unique multiplicative inverse.

3. Fermat's Little Theorem and Euler's Totient Theorem

Fermat's Little Theorem characterizes the periodic nature of powers modulo a prime number $p$:

Euler generalized this to an arbitrary positive modulus $n$ through the Euler totient function $\phi(n)$, which counts how many integers in $\\{1, 2, \ldots, n\\}$ are coprime to $n$. If $n$ has prime factorization $n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$, the totient is calculated as:

Euler's theorem states that for any integer $a$ coprime to $n$:

4. The Order of an Element Modulo n

Let $\gcd(a, n) = 1$. The order of $a$ modulo $n$, denoted $\text{ord}_n(a)$, is defined as the smallest positive integer $d$ such that $a^d \equiv 1 \pmod{n}$. The concept of order has two critical properties that frequently unlock competition problems:

• If $a^k \equiv 1 \pmod{n}$ for some positive integer $k$, then $\text{ord}_n(a)$ must divide $k$.
• Because $a^{\phi(n)} \equiv 1 \pmod{n}$ by Euler's theorem, we always have $\text{ord}_n(a) \mid \phi(n)$. If the modulus is prime $p$, then $\text{ord}_p(a) \mid (p - 1)$.

5. The Lifting the Exponent Lemma (LTE)

Exponential Diophantine equations often feature differences or sums of powers of the form $x^n - y^n$ or $x^n + y^n$. The Lifting the Exponent Lemma (LTE) provides an exact equation for the $p$-adic valuation of such expressions. It is one of the most powerful tools in modern olympiad number theory.

LTE for Odd Primes: The Main Case

Let $p$ be an odd prime. Let $x$ and $y$ be integers such that $p \mid (x - y)$, but $p \nmid x$ and $p \nmid y$. Then for any positive integer $n$:

When $n$ is an odd positive integer and $p \mid (x + y)$ with $p \nmid x$ and $p \nmid y$, substituting $-y$ into the formula yields the plus case:

LTE for the Prime p = 2

The prime $2$ requires special care because the parity of $n$ affects whether intermediate terms are divisible by $4$. Let $x$ and $y$ be odd integers such that $4 \mid (x - y)$. Then for any positive integer $n$:

If $2 \mid (x - y)$ but $4$ does not divide $(x - y)$, then $4 \mid (x + y)$. For even $n$, the formula takes the general form:

6. Worked Olympiad Example Problem

Problem: Find all positive integers $n$ such that $3^n - 1$ is divisible by $2^{2026}$.

Step 1: Reformulate in terms of $2$-adic valuation. The condition that $2^{2026}$ divides $3^n - 1$ translates to:

Step 2: Check the parity of $n$. If $n$ were odd, then $3^n \equiv 3 \equiv (-1)^n \equiv -1 \equiv 3 \pmod 4$, which means $3^n - 1 \equiv 2 \pmod 4$. Consequently, $v_2(3^n - 1) = 1$ for any odd $n$. Since $1 < 2026$, no odd integer $n$ satisfies the condition. Therefore, $n$ must be even.

Step 3: Apply the even-$n$ LTE formula for $p = 2$ with $x = 3$ and $y = 1$. Both $x$ and $y$ are odd integers, and $n$ is even:

Step 4: Substitute the result back into the inequality:

Conclusion: The solutions are all positive integers of the form $n = k \cdot 2^{2024}$, where $k$ is an arbitrary positive integer. Notice how LTE turned an exponential Diophantine divisibility problem into a straightforward linear valuation equation.

Summary for Competition Practice

To develop proficiency in contest number theory, begin by examining small residue classes when analyzing equations. Use modular constraints to eliminate impossible cases, investigate multiplicative orders to understand powers, and apply valuation formulas like LTE when managing varying exponents. Approaching integer problems with these systematic steps builds the precision and confidence required at the national and international olympiad level.