Official IMO Representative for Nepal•नेपाल गणितीय सङ्घ
number_theoryAugust 20, 202612 min read
Elementary Number Theory in Mathematical Olympiads: From Modular Arithmetic to Lifting the Exponent
A structured guide to core and advanced number theory techniques for mathematical competitions, covering divisibility, modular arithmetic, Euler's totient theorem, and the Lifting the Exponent Lemma (LTE) with worked examples.
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=0, we say that a divides b (written a∣b) if there exists an integer k such that b=k⋅a. When a does not divide b, we write a∤b. Every integer divisibility argument rests on two classical results:
Bézout's Identity: gcd(a, b) as a linear combination
The second foundational result is the Fundamental Theorem of Arithmetic: every integer n≥2 can be written uniquely (up to the order of factors) as a product of prime numbers:
Fundamental Theorem of Arithmetic
This canonical factorization introduces the p-adic valuation notation: for a prime p and positive integer n, vp(n) denotes the exponent of the highest power of p dividing n. In other words, vp(n)=α if pα∣n and pα+1∤n. Valuations satisfy two practical rules: vp(ab)=vp(a)+vp(b), and vp(a+b)≥min(vp(a),vp(b)), with equality whenever vp(a)=vp(b).
2. Modular Arithmetic and Residue Systems
Modular arithmetic formalizes the arithmetic of remainders. We write a≡b(modm) if m∣(a−b). Congruence modulo m defines an equivalence relation that respects addition, subtraction, and multiplication. If a≡b(modm) and c≡d(modm), then a+c≡b+d(modm) and ac≡bd(modm). However, division requires caution:
Division Rule in Modular Congruences
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:
Fermat's Little Theorem
Euler generalized this to an arbitrary positive modulus n through the Euler totient function ϕ(n), which counts how many integers in 1,2,…,n are coprime to n. If n has prime factorization n=p1α1⋯pkαk, the totient is calculated as:
Euler's Totient Function Formula
Euler's theorem states that for any integer a coprime to n:
When trying to show an integer equation has no solutions, test small moduli such as 3, 4, 7, 8, or 9. For example, squares can only be 0 or 1(mod3) and (mod4), and 0,1,4, or 7(mod8). Cubes can only be 0,1, or 8(mod9). These constraints frequently rule out infinite families of candidates immediately.
4. The Order of an Element Modulo n
Let gcd(a,n)=1. The order of a modulo n, denoted ordn(a), is defined as the smallest positive integer d such that ad≡1(modn). The concept of order has two critical properties that frequently unlock competition problems:
If ak≡1(modn) for some positive integer k, then ordn(a) must divide k.
Because aϕ(n)≡1(modn) by Euler's theorem, we always have ordn(a)∣ϕ(n). If the modulus is prime p, then ordp(a)∣(p−1).
5. The Lifting the Exponent Lemma (LTE)
Exponential Diophantine equations often feature differences or sums of powers of the form xn−yn or xn+yn. 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∣(x−y), but p∤x and p∤y. Then for any positive integer n:
Lifting the Exponent Lemma (Odd prime p, minus case)
When n is an odd positive integer and p∣(x+y) with p∤x and p∤y, substituting −y into the formula yields the plus case:
Lifting the Exponent Lemma (Odd prime p, odd n, 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∣(x−y). Then for any positive integer n:
LTE for p = 2 when 4 | (x - y)
If 2∣(x−y) but 4 does not divide (x−y), then 4∣(x+y). For even n, the formula takes the general form:
General LTE for p = 2 with even n
Prerequisite Checklist for LTE
Before using LTE in an exam, always state the conditions explicitly: verify that p is a prime, check that p∣(x−y), verify that p∤x and p∤y, and pay attention to whether n is even or odd when handling p=2. Writing out these checks prevents point deductions.
6. Worked Olympiad Example Problem
Problem: Find all positive integers n such that 3n−1 is divisible by 22026.
Step 1: Reformulate in terms of 2-adic valuation. The condition that 22026 divides 3n−1 translates to:
Step 2: Check the parity of n. If n were odd, then 3n≡3≡(−1)n≡−1≡3(mod4), which means 3n−1≡2(mod4). Consequently, v2(3n−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:
Solving for n
Conclusion: The solutions are all positive integers of the form n=k⋅22024, 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.
Number TheoryLTE LemmaModular ArithmeticOlympiad
