`Compfiles/Usa1977P1.lean`

Explanation legend Lean4 Domain Explanation Language (L4DEL)

L4DEL explanations are a separate layer. They do not change the Lean source. Intuition is explanatory prose; numbered items are a reading path; sources link the wording back to evidence.

L4DEL: Lean4 Domain Explanation Language

Annotation provenance. This overlay contains 8 curated AI-written annotations and 3305 mechanical source-derived annotations. They have not been human-reviewed as explanations; treat them as unverified and not mathematical authority. Retained generation history: The 71 original curated annotations were produced in a Claude Sonnet 5.5 session at medium effort; Claude Opus 5.5 is recorded in that session as the advisor model, not the direct author. The bulk source-derived expansion was generated mechanically from pinned source comments by tooling developed in a GPT-5.6 Sol session at ultra reasoning; GPT-5.6 Sol did not originate the quoted source prose. On 2026-10-17 the mechanically generated source-comment annotations of the Formal Conjectures, Carleson, FLT, PFR, CompFiles, Mathematics in Lean and Theorem Proving in Lean overlays were regenerated by the same generator after three corrections made in a Claude Sonnet 5.5 session: titles no longer cut a sentence inside mathematics or end on a dangling word, workflow markers are removed from the quoted prose, and declaration names follow the scanner's namespace resolution. The boilerplate step line was dropped, and comments that were only a row of dashes no longer yield annotations. No new prose was written and no human review is claimed.

Credit: The upstream authors and contributors retain credit for the project and mathematics. lean4-explainer only renders their pinned source and adds the separately disclosed explanation layer.

Project sources: Pinned compfiles documentation, Pinned compfiles corpus index

15 declarations, 0 contain sorry, 0 declared as axioms

USA Mathematical Olympiad 1977, Problem 1

Determine all pairs of positive integers (m, n) such that

1 + x ^ n + x ^ (2 * n) + ... + x ^ (m * n)

is divisible by

1 + x + x ^ 2 + ... + x ^ m.

Imports (10)

Imported by 1 file

Compfiles.lean

def Usa1977P1.geomSumStep line 40 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Polynomial, Int
Proof uses: Finset.sum, Nat, Finset.range, HAdd.hAdd, OfNat.ofNat, HPow.hPow, Polynomial.X, HMul.hMul
14 instances, coercions and auxiliary constants left out.
def Usa1977P1.geomSum line 43 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Polynomial, Int
Proof uses: Finset.sum, Nat, Finset.range, HAdd.hAdd, OfNat.ofNat, HPow.hPow, Polynomial.X
12 instances, coercions and auxiliary constants left out.
lemma Usa1977P1.coeff_geomSum line 48 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Nat, Eq, Int, Finsupp, Polynomial.coeff, Usa1977P1.geomSum, ite, LE.le, OfNat.ofNat
Proof uses: of_eq_true, Eq.trans, True, congrFun', congrArg, Finset.sum, Polynomial, Finset.range, HAdd.hAdd, HPow.hPow, Polynomial.X, Polynomial.finsetSum_coeff, Membership.mem, Finset, Finset.sum_congr, Eq.refl, Polynomial.coeff_X_pow, Finset.sum_ite_eq, ite_congr, LT.lt and 2 more
44 instances, coercions and auxiliary constants left out.

Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
lemma Usa1977P1.geomSum_natDegree line 53 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Eq, Nat, Polynomial.natDegree, Int, Usa1977P1.geomSum
Proof uses: le_antisymm, Eq.mpr, LE.le, LT.lt, Finsupp, Polynomial.coeff, OfNat.ofNat, id, congrArg, propext, Polynomial.natDegree_le_iff_coeff_eq_zero, ite, Usa1977P1.coeff_geomSum, ite_eq_right, Eq.refl, Polynomial.le_natDegree_of_ne_zero, of_eq_true, Ne, Eq.trans, True and 5 more
28 instances, coercions and auxiliary constants left out.

Tactic trace: 9 steps
Open to load the checked before-and-after goal states.
lemma Usa1977P1.geomSum_monic line 60 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Polynomial.Monic, Int, Usa1977P1.geomSum
Proof uses: id, Eq.mpr, Eq, Finsupp, Nat, Polynomial.coeff, Polynomial.natDegree, OfNat.ofNat, congrArg, Usa1977P1.geomSum_natDegree, of_eq_true, Eq.trans, True, congrFun', ite, LE.le, Usa1977P1.coeff_geomSum, ite_eq_left_of_eq_true, eq_self
13 instances, coercions and auxiliary constants left out.

Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
lemma Usa1977P1.map_geomSum line 65 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Eq, Polynomial, Complex, Polynomial.map, Int, Int.castRingHom, Usa1977P1.geomSum, Finset.sum, Nat, Finset.range, HAdd.hAdd, OfNat.ofNat, HPow.hPow, Polynomial.X
Proof uses: id, Eq.mpr, congrArg, Polynomial.map_sum, of_eq_true, Eq.trans, True, congrFun', Finset.sum_congr, Eq.refl, Finset, Membership.mem, Polynomial.map_pow, Polynomial.map_X, eq_self
32 instances, coercions and auxiliary constants left out.

Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
lemma Usa1977P1.map_geomSumStep line 72 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Eq, Polynomial, Complex, Polynomial.map, Int, Int.castRingHom, Usa1977P1.geomSumStep, Finset.sum, Nat, Finset.range, HAdd.hAdd, OfNat.ofNat, HPow.hPow, Polynomial.X
Proof uses: id, Eq.mpr, HMul.hMul, congrArg, Polynomial.map_sum, congrFun', Finset.sum_congr, Eq.refl, Finset, Membership.mem, Eq.trans, Polynomial.map_pow, Polynomial.map_X, rfl, mul_comm, pow_mul
39 instances, coercions and auxiliary constants left out.

Tactic trace: 6 steps
Open to load the checked before-and-after goal states.
lemma Usa1977P1.eval_map_geomSum line 82 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Complex, Ne, OfNat.ofNat, Eq, Polynomial.eval, Polynomial.map, Int, Int.castRingHom, Usa1977P1.geomSum, HDiv.hDiv, HSub.hSub, HPow.hPow, Nat, HAdd.hAdd
Proof uses: Eq.mpr, Finset.sum, Polynomial, Finset.range, Polynomial.X, id, congrArg, Usa1977P1.map_geomSum, congrFun', Eq.trans, Polynomial.eval_finsetSum, Finset.sum_congr, Eq.refl, Finset, Membership.mem, Polynomial.eval_pow, Polynomial.eval_X, geom_sum_eq
48 instances, coercions and auxiliary constants left out.

Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
lemma Usa1977P1.eval_map_geomSumStep line 88 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Complex, Ne, HPow.hPow, Nat, OfNat.ofNat, Eq, Polynomial.eval, Polynomial.map, Int, Int.castRingHom, Usa1977P1.geomSumStep, HDiv.hDiv, HSub.hSub, HAdd.hAdd
Proof uses: Eq.mpr, Finset.sum, Polynomial, Finset.range, Polynomial.X, id, congrArg, Usa1977P1.map_geomSumStep, congrFun', Eq.trans, Polynomial.eval_finsetSum, Finset.sum_congr, Eq.refl, Finset, Membership.mem, Polynomial.eval_pow, Polynomial.eval_X, geom_sum_eq
48 instances, coercions and auxiliary constants left out.

Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
lemma Usa1977P1.eval_map_geomSumStep_of_pow_eq_one line 95 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Complex, Eq, HPow.hPow, Nat, OfNat.ofNat, Polynomial.eval, Polynomial.map, Int, Int.castRingHom, Usa1977P1.geomSumStep, HAdd.hAdd
Proof uses: Eq.mpr, Finset.sum, Polynomial, Finset.range, Polynomial.X, id, congrArg, Usa1977P1.map_geomSumStep, congrFun', Eq.trans, Polynomial.eval_finsetSum, Finset.sum_congr, Eq.refl, Finset, Membership.mem, Polynomial.eval_pow, Polynomial.eval_X, rfl, one_pow, HSMul.hSMul and 6 more
60 instances, coercions and auxiliary constants left out.

Tactic trace: 5 steps
Open to load the checked before-and-after goal states.
lemma Usa1977P1.dvd_iff_map_dvd Divisibility over ℤ transfers to divisibility over ℂ, since the divisor is monic line 105 source
Source documentation
Divisibility over ℤ transfers to divisibility over ℂ, since the divisor is monic.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Iff, Dvd.dvd, Polynomial, Int, Usa1977P1.geomSum, Usa1977P1.geomSumStep, Complex, Polynomial.map, Int.castRingHom
Proof uses: Iff.symm, Polynomial.map_dvd_map, Int.cast_injective, Usa1977P1.geomSum_monic
26 instances, coercions and auxiliary constants left out.
```
lemma dvd_iff_map_dvd (m n : ℕ+) :
    geomSum m ∣ geomSumStep m n ↔
      (geomSum m).map (Int.castRingHom ℂ) ∣ (geomSumStep m n).map (Int.castRingHom ℂ) :=
…
```
Mentions: Usa1977P1.geomSum, Usa1977P1.geomSumStep
lemma Usa1977P1.not_dvd_of_gcd_ne_one If gcd (m+1) n ≠ 1, divisibility fails: the (m+1)/gcd-th power of a primitive (m+1)-th root of unity is a root of the divisor but not of the dividend line 112 source
Source documentation
If gcd (m+1) n ≠ 1, divisibility fails: the (m+1)/gcd-th power of a primitive (m+1)-th root of unity is a root of the divisor but not of the dividend.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Ne, Nat, Nat.gcd, HAdd.hAdd, OfNat.ofNat, Not, Dvd.dvd, Polynomial, Int, Usa1977P1.geomSum, Usa1977P1.geomSumStep
Proof uses: LE.le, LT.lt, PNat.pos, Eq, rfl, Nat.gcd_dvd_left, Nat.gcd_dvd_right, Nat.gcd_pos_of_pos_left, Eq.mp, congrArg, HDiv.hDiv, Nat.div_pos, Nat.le_of_dvd, HMul.hMul, Nat.div_mul_cancel, Trans.trans, Nat.mul_le_mul_right, Eq.mpr, id, mul_comm and 36 more
104 instances, coercions and auxiliary constants left out.

Tactic trace: 52 steps
Open to load the checked before-and-after goal states.
```
lemma not_dvd_of_gcd_ne_one {m n : ℕ+} (hgcd : Nat.gcd ((m : ℕ) + 1) (n : ℕ) ≠ 1) :
    ¬ (geomSum m ∣ geomSumStep m n) := by
…
```
Mentions: Usa1977P1.geomSum, Usa1977P1.geomSumStep
lemma Usa1977P1.dvd_of_gcd_eq_one If gcd (m+1) n = 1, divisibility holds: the remainder of the division vanishes at all m nontrivial (m+1)-th roots of unity, and has degree < m, hence is zero line 163 source
Source documentation
If gcd (m+1) n = 1, divisibility holds: the remainder of the division vanishes at all m nontrivial (m+1)-th roots of unity, and has degree < m, hence is zero.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Eq, Nat, Nat.gcd, HAdd.hAdd, OfNat.ofNat, Dvd.dvd, Polynomial, Int, Usa1977P1.geomSum, Usa1977P1.geomSumStep
Proof uses: Eq.mpr, Complex, Polynomial.map, Int.castRingHom, id, congrArg, propext, Usa1977P1.dvd_iff_map_dvd, LE.le, LT.lt, PNat.pos, Nat.Coprime, Complex.exp, HDiv.hDiv, HMul.hMul, Real.pi, Complex.I, rfl, IsPrimitiveRoot, Complex.isPrimitiveRoot_exp and 51 more
133 instances, coercions and auxiliary constants left out.

Tactic trace: 61 steps
Open to load the checked before-and-after goal states.
```
lemma dvd_of_gcd_eq_one {m n : ℕ+} (hgcd : Nat.gcd ((m : ℕ) + 1) (n : ℕ) = 1) :
    geomSum m ∣ geomSumStep m n := by
…
```
Mentions: Usa1977P1.geomSum, Usa1977P1.geomSumStep
determine Usa1977P1.solution_set line 230 source
no axioms what this means
Statement uses: Set, Prod, PNat
Proof uses: Set.ofPred, Nat.Coprime, HAdd.hAdd, Nat, Prod.fst, OfNat.ofNat, Prod.snd
4 instances, coercions and auxiliary constants left out.
problem Usa1977P1.usa1977_p1 line 232 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: PNat, Iff, Membership.mem, Prod, Set, Usa1977P1.solution_set, Prod.mk, Dvd.dvd, Polynomial, Int, Usa1977P1.geomSum, Usa1977P1.geomSumStep
Proof uses: id, Iff.intro, Nat.Coprime, HAdd.hAdd, Nat, OfNat.ofNat, Usa1977P1.dvd_of_gcd_eq_one, Decidable.byContradiction, Not, Usa1977P1.not_dvd_of_gcd_ne_one
25 instances, coercions and auxiliary constants left out.

Tactic trace: 8 steps
Open to load the checked before-and-after goal states.