`Compfiles/Imo1977P3.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

8 declarations, 0 contain sorry, 0 declared as axioms

International Mathematical Olympiad 1977, Problem 3

Given an integer n > 2, let Vₙ be the set of integers 1 + kn for k a positive integer. A number m in Vₙ is called indecomposable if it cannot be expressed as the product of two members of Vₙ. Prove that there is a number in Vₙ which can be expressed as the product of indecomposable members of Vₙ in more than one way (decompositions which differ solely in the order of factors are not regarded as different).

Imports (2)

Imported by 1 file

Compfiles.lean

def Imo1977P3.Vn The set Vₙ of natural numbers of the form 1 + k * n with k a positive integer line 31 source
Source documentation
The set Vₙ of natural numbers of the form 1 + k * n with k a positive integer.

no axioms what this means
Statement uses: Nat, Set
Proof uses: Set.ofPred, Exists, And, LE.le, OfNat.ofNat, Eq, HAdd.hAdd, HMul.hMul
6 instances, coercions and auxiliary constants left out.
```
def Vn (n : ℕ) : Set ℕ := {m | ∃ k : ℕ, 1 ≤ k ∧ m = 1 + k * n}
```
def Imo1977P3.Indecomposable m is indecomposable in Vₙ if it belongs to Vₙ but cannot be written as a product of two members of Vₙ line 35 source
Source documentation
m is indecomposable in Vₙ if it belongs to Vₙ but cannot be written as a product of two members of Vₙ.

no axioms what this means
Statement uses: Nat
Proof uses: And, Membership.mem, Set, Imo1977P3.Vn, Not, Exists, Eq, HMul.hMul
3 instances, coercions and auxiliary constants left out.
```
def Indecomposable (n : ℕ) (m : ℕ) : Prop :=
…
```
lemma Imo1977P3.vn_ge Every member of Vₙ is at least n + 1 line 41 source
Source documentation
Every member of Vₙ is at least n + 1.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Nat, Membership.mem, Set, Imo1977P3.Vn, LE.le, HAdd.hAdd, OfNat.ofNat
Proof uses: And, Eq, HMul.hMul, Nat.mul_le_mul, le_refl, Eq.symm
17 instances, coercions and auxiliary constants left out.

Tactic trace: 3 steps
Open to load the checked before-and-after goal states.
```
lemma vn_ge {n m : ℕ} (hm : m ∈ Vn n) : n + 1 ≤ m := by
…
```
Mentions: Imo1977P3.Vn
lemma Imo1977P3.mul_mem_vn Vₙ is closed under multiplication line 47 source
Source documentation
Vₙ is closed under multiplication.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Nat, Membership.mem, Set, Imo1977P3.Vn, HMul.hMul
Proof uses: And, LE.le, OfNat.ofNat, Eq, HAdd.hAdd, Exists.intro, And.intro, Mathlib.Tactic.Ring.of_eq, Nat.rawCast, HPow.hPow, Mathlib.Tactic.Ring.Common.mul_congr, Mathlib.Tactic.Ring.Common.add_congr, Mathlib.Tactic.Ring.cast_pos, Mathlib.Meta.NormNum.isNat_ofNat, Eq.refl, Mathlib.Tactic.Ring.Common.atom_pf, rfl, Eq.mpr, id, congrArg and 16 more
30 instances, coercions and auxiliary constants left out.

Tactic trace: 5 steps
Open to load the checked before-and-after goal states.
```
lemma mul_mem_vn {n p q : ℕ} (hp : p ∈ Vn n) (hq : q ∈ Vn n) : p * q ∈ Vn n := by
…
```
Mentions: Imo1977P3.Vn
lemma Imo1977P3.indecomposable_sq (n - 1)^2 (written with n = c + 3) is indecomposable in Vₙ: it is smaller than the square of the smallest member of Vₙ line 54 source
Source documentation
(n - 1)^2 (written with n = c + 3) is indecomposable in Vₙ: it is smaller than the square of the smallest member of Vₙ.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Nat, Imo1977P3.Indecomposable, HAdd.hAdd, OfNat.ofNat, HPow.hPow
Proof uses: And.intro, Membership.mem, Set, Imo1977P3.Vn, Not, Exists, And, Eq, HMul.hMul, Exists.intro, LE.le, Mathlib.Tactic.Ring.of_eq, Nat.rawCast, Mathlib.Tactic.Ring.Common.pow_congr, Mathlib.Tactic.Ring.Common.add_congr, Mathlib.Tactic.Ring.Common.atom_pf, rfl, Eq.mpr, id, congrArg and 34 more
36 instances, coercions and auxiliary constants left out.

Tactic trace: 16 steps
Open to load the checked before-and-after goal states.
```
lemma indecomposable_sq (c : ℕ) : Indecomposable (c + 3) ((c + 2) ^ 2) := by
…
```
Mentions: Imo1977P3.Indecomposable
lemma Imo1977P3.not_dvd (n - 1)^2 does not divide (n - 1) * (2 * n - 1) (written with n = c + 3), since n - 1 does not divide 2 * n - 1 = 2 * (n - 1) + 1 line 67 source
Source documentation
(n - 1)^2 does not divide (n - 1) * (2 * n - 1) (written with n = c + 3), since n - 1 does not divide 2 * n - 1 = 2 * (n - 1) + 1.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Nat, Not, Dvd.dvd, HPow.hPow, HAdd.hAdd, OfNat.ofNat, HMul.hMul
Proof uses: Nat.dvd_of_mul_dvd_mul_left, Eq.mp, congrArg, sq, HSub.hSub, Nat.dvd_sub, dvd_mul_left, Eq, LE.le, Nat.le_of_dvd, one_pos
37 instances, coercions and auxiliary constants left out.

Tactic trace: 12 steps
Open to load the checked before-and-after goal states.
```
lemma not_dvd (c : ℕ) : ¬ (c + 2) ^ 2 ∣ (c + 2) * (2 * c + 5) := by
…
```
lemma Imo1977P3.exists_factorization Every member of Vₙ is a product of indecomposable members of Vₙ line 80 source
Source documentation
Every member of Vₙ is a product of indecomposable members of Vₙ.

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Nat, LT.lt, OfNat.ofNat, Membership.mem, Set, Imo1977P3.Vn, Exists, Multiset, And, Imo1977P3.Indecomposable, Eq, Multiset.prod
Proof uses: Nat.strong_induction_on, dite, Classical.propDecidable, Exists.intro, Singleton.singleton, And.intro, Eq.mpr, id, congrArg, Eq.mp, propext, Multiset.mem_singleton, Multiset.prod_singleton, Not, HMul.hMul, Classical.byContradiction, LE.le, HAdd.hAdd, Imo1977P3.vn_ge, Nat.mul_le_mul and 8 more
28 instances, coercions and auxiliary constants left out.

Tactic trace: 27 steps
Open to load the checked before-and-after goal states.
```
lemma exists_factorization (n : ℕ) (hn : 2 < n) :
    ∀ m : ℕ, m ∈ Vn n →
      ∃ F : Multiset ℕ, (∀ d ∈ F, Indecomposable n d) ∧ F.prod = m := by
…
```
Mentions: Imo1977P3.Vn, Imo1977P3.Indecomposable
problem Imo1977P3.imo1977_p3 line 109 source
standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Nat, LT.lt, OfNat.ofNat, Exists, And, Membership.mem, Set, Imo1977P3.Vn, Multiset, Imo1977P3.Indecomposable, Eq, Multiset.prod, Ne
Proof uses: HAdd.hAdd, Exists.intro, HSub.hSub, HPow.hPow, LE.le, HMul.hMul, And.intro, Mathlib.Tactic.Ring.of_eq, Nat.rawCast, Mathlib.Tactic.Ring.Common.pow_congr, Mathlib.Tactic.Ring.Common.add_congr, Mathlib.Tactic.Ring.Common.atom_pf, rfl, Eq.mpr, id, congrArg, Eq.symm, Eq.refl, Mathlib.Tactic.Ring.cast_pos, Mathlib.Meta.NormNum.isNat_ofNat and 42 more
50 instances, coercions and auxiliary constants left out.

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