The lifting-the-exponent lemma (odd primes)
ProvedFamousTheorems.lifting_the_exponentThe lifting-the-exponent lemma (odd primes). Let be an odd prime and integers with and . Then for every ,
The lemma computes exactly how divisible is by powers of . It is a standard tool in olympiad number theory and in the study of orders of elements modulo prime powers. It gives, for example, the order of modulo and the structure of .
Formalization note. Mathlib's Int.emultiplicity_pow_sub_pow. The valuations are written with emultiplicity, which takes values in ℕ∞ and is infinite exactly for the value (for example when ). The prime is a natural number cast to ℤ in the divisibility hypotheses, and is computed in ℕ.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem lifting_the_exponent {p : ℕ} (hp : p.Prime) (hp1 : Odd p) {x y : ℤ} (hxy : (p : ℤ) ∣ x - y) (hx : ¬(p : ℤ) ∣ x) (n : ℕ) :
emultiplicity (p : ℤ) (x ^ n - y ^ n) = emultiplicity (p : ℤ) (x - y) + emultiplicity p n := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Int.emultiplicity_pow_sub_pow`. Proof here reduces to that Mathlib result.