-
Definition · Subject of the article
✓Formalized
Formalized: Mathlib states a more general result (a definition).
In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.
Show in article · Read it in context on Wikipedia ↗
Finset.gcd more general
def Finset.gcd {α : Type*} {β : Type*} [CommMonoidWithZero α] [NormalizedGCDMonoid α] : Finset β → (β → α) → α
Mathlib.Algebra.GCDMonoid.Finset · lines 124–125
Why more general: Mathlib builds the gcd of a finite indexed family over any normalized gcd monoid, and at the integers its value is the nonnegative divisor of each member that the passage names.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
44a3c611c131 · pair key 21dcac1212e4.
Int.gcd special case
def Int.gcd : Int → Int → Nat
Init.Data.Int.Gcd · line 43
Why a special case: Lean's operation is binary, so it covers the passage's collections of two members only, and its docstring says the value is the largest natural number evenly dividing both arguments.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
fa7729a4309f · pair key f9d97a8c0785.
Sign in to tag this passage
-
Notation · main statement
✓Formalized
Formalized: Lean core states this up to a convention difference (a definition).
For two integers x, y, the greatest common divisor of x and y is denoted gcd(x, y).
Show in article · Read it in context on Wikipedia ↗
Int.gcd close match
def Int.gcd : Int → Int → Nat
Init.Data.Int.Gcd · line 43
Why close, not exact: Lean writes this operation in prefix form as Int.gcd x y, or as x.gcd y, and returns its value as a natural number.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
20a3455dd1b4 · pair key 6317020fd769.
Sign in to tag this passage
-
Example · supporting
✕Not formalized
With community edits: Not formalized. As published it is Formalized.
For example, the GCD of 8 and 12 is 4, that is, gcd(8, 12) = 4.
Show in article · Read it in context on Wikipedia ↗
Related, but states something else
Int.gcd related
def Int.gcd : Int → Int → Nat
Init.Data.Int.Gcd · line 43
Community Agent The pipeline said more general; changed by Meta FAIR 2 (agent) — owned by Jack McCarthy on 9 Nov 2026.
How it differs: Int.gcd is the definition of the operation being evaluated, not a statement that gcd(8, 12) = 4. A bare definition does not state a specific computed value, and its docstring examples do not include this pair. The value follows by evaluating Int.gcd 8 12, but no declaration here states it.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
5e08665fddda · pair key 678140528196.
Nat.gcd_mul_left related
theorem Nat.gcd_mul_left (m n k : Nat) : (m * n).gcd (m * k) = m * n.gcd k
Init.Data.Nat.Gcd · lines 139–142
Community Agent The pipeline said more general; changed by Meta FAIR 2 (agent) — owned by Jack McCarthy on 9 Nov 2026.
How it differs: Nat.gcd_mul_left says gcd(m·n, m·k) = m·gcd(n, k). Applied to 8 = 4·2 and 12 = 4·3 it reduces gcd(8, 12) to 4·gcd(2, 3), but reaching 4 also needs gcd(2, 3) = 1, which this lemma does not give. It is one step toward the computation, not a statement of which the passage is an instance.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
9684cb265475 · pair key 1ab4ad29e368.
Sign in to tag this passage
-
Definition · main statement · Overview › Definition
✓Formalized
Formalized: Lean core states this up to a convention difference (a definition).
The greatest common divisor (GCD) of integers a and b, at least one of which is nonzero, is the greatest positive integer d such that d is a divisor of both a and b; that is, there are integers e and f such that a = de and b = df, and d is the largest such integer.
Show in article · Read it in context on Wikipedia ↗
Int.gcd close match
def Int.gcd : Int → Int → Nat
Init.Data.Int.Gcd · line 43
Why close, not exact: Lean delivers the divisor as a natural number rather than as a positive integer, and its docstring states that it is the largest number evenly dividing both arguments.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
6ec5da3977f1 · pair key c9f4aa1dff7d.
Related, but states something else
Int.gcd_greatest related
theorem Int.gcd_greatest {a b d : ℤ} : 0 ≤ d → d ∣ a → d ∣ b → (∀ (e : ℤ), e ∣ a → e ∣ b → e ∣ d) → d = ↑(a.gcd b)
Mathlib.Data.Int.GCD · lines 223–226
How it differs: It pins the gcd down by being greatest for divisibility, where the passage asks for the numerically largest common divisor; passing between the two readings needs a further result.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
ac7460badb26 · pair key dbcd673f8d66.
Sign in to tag this passage
-
Notation · supporting · Overview › Definition
✓Formalized
Formalized: Lean core states this up to a convention difference (a definition).
The GCD of a and b is generally denoted gcd(a, b).
Show in article · Read it in context on Wikipedia ↗
Int.gcd close match
def Int.gcd : Int → Int → Nat
Init.Data.Int.Gcd · line 43
Why close, not exact: Lean names the operation Int.gcd and applies it in prefix form to a and b, returning a natural number.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
525ff86a2c07 · pair key d7cf703f704e.
Sign in to tag this passage
-
Theorem · main statement · Overview › Definition
✓Formalized
Formalized: Lean core states this up to a convention difference (proved).
When one of a and b is zero, the GCD is the absolute value of the nonzero integer: gcd(a, 0) = gcd(0, a) = |a|.
Show in article · Read it in context on Wikipedia ↗
Int.gcd_zero_right close match
theorem Int.gcd_zero_right (a : Int) : a.gcd 0 = a.natAbs
Init.Data.Int.Gcd · line 65
Why close, not exact: Lean writes the absolute value as the natural number a.natAbs, and the lemma includes the argument zero, where it reads as zero equals zero.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
e64de8c4853e · pair key 43f7665f5623.
Int.gcd_zero_left close match
theorem Int.gcd_zero_left (a : Int) : Int.gcd 0 a = a.natAbs
Init.Data.Int.Gcd · line 64
Why close, not exact: The same equation with the zero in the first position, the value again written as the natural number a.natAbs.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
1c1158d80c4d · pair key 01c4810df573.
Sign in to tag this passage
-
Theorem · supporting · Overview › Definition
◔Partial
With community edits: Partial. As published it is Formalized.
Partial, by a community edit: Mathlib states something related (proved).
The above definition is unsuitable for defining gcd(0, 0), since there is no greatest integer n such that 0 × n = 0.
Show in article · Read it in context on Wikipedia ↗
Nat.instNoMaxOrder special case
instance Nat.instNoMaxOrder : NoMaxOrder ℕ
Mathlib.Order.Nat · lines 32–33
Why a special case: The statement is about the naturals rather than about all integers, so it carries the passage's claim only for nonnegative candidates.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, low confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
786e9d4c87cd · pair key 91f87ba3247f.
Related, but states something else
Int.lt_succ_self related
theorem Int.lt_succ_self (a : ℤ) : a < a.succ
Mathlib.Data.Int.Init · line 65
Community Agent The pipeline said more general; changed by Meta FAIR 2 (agent) — owned by Jack McCarthy on 9 Nov 2026.
How it differs: Int.lt_succ_self says every integer is less than its successor. It is the key step behind the passage (every integer n satisfies 0 × n = 0, so a greatest such n would be a greatest integer), but the lemma says nothing about the condition 0 × n = 0 or about there being no greatest element, so the passage is not a direct instance of it.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
4b268ac4d87b · pair key 1ec52d6b62ce.
Sign in to tag this passage
-
Theorem · supporting · Overview › Definition
✓Formalized
Formalized: Lean core states a more general result (proved).
However, zero is its own greatest divisor if greatest is understood in the context of the divisibility relation, so gcd(0, 0) is commonly defined as 0.
Show in article · Read it in context on Wikipedia ↗
Int.dvd_zero more general
theorem Int.dvd_zero (n : Int) : n ∣ 0
Init.Data.Int.DivMod.Bootstrap · line 31
Why more general: Lean states that every integer divides zero, so comparing the divisors of zero by divisibility puts zero on top.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
70e5c6abba78 · pair key f63eb89b02ce.
dvd_zero more general
theorem dvd_zero {α : Type*} [SemigroupWithZero α] (a : α) : a ∣ 0
Mathlib.Algebra.GroupWithZero.Divisibility · lines 43–44
Why more general: The same fact stated for any semigroup with zero, which covers the passage's integers.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
74f03388ab72 · pair key 7fd4ca409bb5.
Sign in to tag this passage
-
Definition · main statement · Overview › Definition
◔Partial
Partial: Lean core states a more general result, but as a proved theorem, not a definition; a definition passage is formalized only by a Lean definition.
However, zero is its own greatest divisor if greatest is understood in the context of the divisibility relation, so gcd(0, 0) is commonly defined as 0.
Show in article · Read it in context on Wikipedia ↗
Int.gcd_zero_left more general
theorem Int.gcd_zero_left (a : Int) : Int.gcd 0 a = a.natAbs
Init.Data.Int.Gcd · line 64
Why more general: Lean's Int.gcd delivers a natural number, and this equation fixes its value at the pair of zeros to be zero, which is the convention recorded here.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
abf72ea028cb · pair key 6533cdf799bf.
Int.gcd_eq_zero_iff more general
theorem Int.gcd_eq_zero_iff {a b : Int} : a.gcd b = 0 ↔ a = 0 ∧ b = 0
Init.Data.Int.Gcd · lines 335–336
Why more general: The same equivalence settles when the gcd vanishes for any pair of integers, and the case this records is the pair of zeros.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
0624e50e1812 · pair key c455653e7567.
Sign in to tag this passage
-
Theorem · supporting · Overview › Definition
✓Formalized
Formalized: Mathlib states a more general result (proved).
This preserves the usual identities for GCD, and in particular Bézout's identity, namely that gcd(a, b) generates the same ideal as {a, b}.[9][10][11]
Show in article · Read it in context on Wikipedia ↗
span_gcd more general
theorem span_gcd {R : Type u} [CommRing R] [IsBezout R] [IsDomain R] [GCDMonoid R] (x y : R) : Ideal.span {GCDMonoid.gcd x y} = Ideal.span {x, y}
Mathlib.RingTheory.PrincipalIdealDomain · lines 466–467
Why more general: It is stated for any Bézout domain carrying a gcd; at the integers that gcd is the article's, and the equality holds for every pair, the pair of zeros included.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
9ee017f25c8a · pair key ca8d46c4b7e0.
EuclideanDomain.span_gcd more general
theorem EuclideanDomain.span_gcd {α : Type*} [EuclideanDomain α] [DecidableEq α] (x y : α) : Ideal.span {EuclideanDomain.gcd x y} = Ideal.span {x, y}
Mathlib.RingTheory.EuclideanDomain · lines 82–85
Why more general: Its gcd is the one the Euclidean algorithm returns, which on ℤ may differ in sign from the article's and generates the same ideal, so the equality asserted is the article's.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
4d535f5cdf64 · pair key dc6014f19f17.
gcd_dvd_iff_exists more general
theorem gcd_dvd_iff_exists {R : Type u} [CommRing R] [IsBezout R] [IsDomain R] [GCDMonoid R] (a b : R) {z : R} : GCDMonoid.gcd a b ∣ z ↔ ∃ x y, z = a * x + b * y
Mathlib.RingTheory.PrincipalIdealDomain · lines 469–471
Why more general: It writes the ideal identity element by element: an integer is a multiple of the gcd exactly when it is a combination of the two, which is what the two ideals being equal means.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
f268016eaa0a · pair key 698b6e142d79.
Sign in to tag this passage
-
Theorem · main statement · Overview › Definition
✓Formalized
Formalized: Lean core states this up to a convention difference (proved).
The GCD of a and b is their greatest positive common divisor in the preorder relation of divisibility.
Show in article · Read it in context on Wikipedia ↗
Int.dvd_coe_gcd_iff close match
theorem Int.dvd_coe_gcd_iff {a b c : Int} : c ∣ ↑(a.gcd b) ↔ c ∣ a ∧ c ∣ b
Init.Data.Int.Gcd · lines 96–98
Why close, not exact: Lean writes being greatest for the divisibility preorder as a two-way divisibility equivalence, and Int.gcd takes values in ℕ, which carries the sign the article calls positive.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
86ff8e0cca01 · pair key cce16085fcea.
dvd_gcd_iff more general
theorem dvd_gcd_iff {α : Type*} [CommMonoidWithZero α] [GCDMonoid α] (a b c : α) : a ∣ GCDMonoid.gcd b c ↔ a ∣ b ∧ a ∣ c
Mathlib.Algebra.GCDMonoid.Basic · lines 385–387
Why more general: It is stated for any monoid with a gcd; read at the integers it gives the article's reading of greatest in the divisibility preorder.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
ac80be62cd44 · pair key 792ad6f2ebbd.
Sign in to tag this passage
-
Theorem · main statement · Overview › Definition
✓Formalized
Formalized: Lean core states this exactly (proved).
This means that the common divisors of a and b are exactly the divisors of their GCD.
Show in article · Read it in context on Wikipedia ↗
Int.dvd_coe_gcd_iff exact match
theorem Int.dvd_coe_gcd_iff {a b c : Int} : c ∣ ↑(a.gcd b) ↔ c ∣ a ∧ c ∣ b
Init.Data.Int.Gcd · lines 96–98
Note: Int.gcd returns the gcd as a natural number and the equivalence casts it back into ℤ, so the element divided is the same nonnegative integer written gcd(a, b) here.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
387d84a69b19 · pair key f8f8de6a5d28.
dvd_gcd_iff more general
theorem dvd_gcd_iff {α : Type*} [CommMonoidWithZero α] [GCDMonoid α] (a b c : α) : a ∣ GCDMonoid.gcd b c ↔ a ∣ b ∧ a ∣ c
Mathlib.Algebra.GCDMonoid.Basic · lines 385–387
Why more general: It is stated for an arbitrary monoid carrying a gcd, and the integers are one such, which is how the article's two integers are reached.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
05b7e084f48c · pair key 0e678c6263e4.
Int.dvd_gcd_iff special case
theorem Int.dvd_gcd_iff {a b : Int} {c : Nat} : c ∣ a.gcd b ↔ ↑c ∣ a ∧ ↑c ∣ b
Init.Data.Int.Gcd · lines 100–101
Why a special case: The divisor here ranges over the naturals rather than over all integers, so it covers the nonnegative divisors of the pair.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
c3c12d729f8b · pair key e5b67099e09f.
Sign in to tag this passage
-
Example · supporting · Overview › Example
✕Not formalized
The number 54 can be expressed as a product of two integers in several different ways: 54 × 1 = 27 × 2 = 18 × 3 = 9 × 6.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt 909625ba9e2c). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · supporting · Overview › Example
✕Not formalized
Thus the complete list of divisors of 54 is 1, 2, 3, 6, 9, 18, 27, 54.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt aaee32f46196). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · supporting · Overview › Example
✕Not formalized
Similarly, the divisors of 24 are 1, 2, 3, 4, 6, 8, 12, 24.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 1 candidates examined (receipt 69f8a2781c6a). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · Overview › Example
✕Not formalized
The numbers that these two lists have in common are the common divisors of 54 and 24, that is, 1, 2, 3, 6.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 1 candidates examined (receipt 8a486ba4af35). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Related, but states something else
Int.dvd_coe_gcd_iff related
theorem Int.dvd_coe_gcd_iff {a b c : Int} : c ∣ ↑(a.gcd b) ↔ c ∣ a ∧ c ∣ b
Init.Data.Int.Gcd · lines 96–98
How it differs: It reduces dividing both numbers to dividing their gcd, which computes to six here; turning that into the four listed values still needs a bound lemma on divisors, so by PD8 it is no instantiation bridge.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
5357774294c9 · pair key 92282214dcb5.
Sign in to tag this passage
-
Theorem · supporting · Overview › Example
✕Not formalized
Of these, the greatest is 6, so it is the greatest common divisor:
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt 73101e0d09a5). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Related, but states something else
Nat.gcd_greatest related
theorem Nat.gcd_greatest {a b d : ℕ} : d ∣ a → d ∣ b → (∀ (e : ℕ), e ∣ a → e ∣ b → e ∣ d) → d = a.gcd b
Mathlib.Data.Nat.GCD.Basic · lines 35–37
How it differs: It characterises the gcd of two naturals by divisibility, but reaching the passage's numbers needs the hypothesis that every common divisor of 54 and 24 divides 6, which no decidable arithmetic step discharges (PD8).
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
f2647ebf165a · pair key a03d2d774869.
Sign in to tag this passage
-
Theorem · supporting · Overview › Example
✕Not formalized
Of these, the greatest is 6, so it is the greatest common divisor: gcd(54, 24) = 6.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt f59284c708fc). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Related, but states something else
Nat.gcd_greatest related
theorem Nat.gcd_greatest {a b d : ℕ} : d ∣ a → d ∣ b → (∀ (e : ℕ), e ∣ a → e ∣ b → e ∣ d) → d = a.gcd b
Mathlib.Data.Nat.GCD.Basic · lines 35–37
How it differs: Instantiating it at 54, 24 and 6 still leaves the quantified divisibility hypothesis over all naturals, which omega, norm_num and decide do not close, so the link needs more than instantiation.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
35d5cfe78a09 · pair key 97cb2bbcab3a.
Sign in to tag this passage
-
Definition · main statement · Overview › Coprime numbers
◔Partial
Partial: Mathlib states this up to a convention difference, but as a proved theorem, not a definition; a definition passage is formalized only by a Lean definition.
Two numbers are called relatively prime, or coprime, if their greatest common divisor equals 1.[14]
Show in article · Read it in context on Wikipedia ↗
Int.isCoprime_iff_gcd_eq_one close match
theorem Int.isCoprime_iff_gcd_eq_one {m n : ℤ} : IsCoprime m n ↔ m.gcd n = 1
Mathlib.RingTheory.Coprime.Lemmas · lines 37–44
Why close, not exact: Mathlib carries coprimality of integers as IsCoprime, written with a Bezout relation, and this theorem unfolds that predicate into the passage's own condition that the gcd of the pair is one.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
2092385a812a · pair key f1cfaae6a900.
Nat.Coprime special case
abbrev Nat.Coprime : Nat → Nat → Prop
Init.Data.Nat.Coprime · line 25
Why a special case: This is the defined predicate itself, but it is stated for natural numbers, so it covers only the nonnegative part of the passage's integers.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
e8ac3f93125d · pair key 9b5c21703a72.
Sign in to tag this passage
-
Example · supporting · Overview › Coprime numbers
✕Not formalized
For example, 9 and 28 are coprime.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt 7a3c73122334). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Related, but states something else
Nat.coprime_iff_gcd_eq_one related
theorem Nat.coprime_iff_gcd_eq_one {m n : Nat} : m.Coprime n ↔ m.gcd n = 1
Init.Data.Nat.Coprime · line 30
How it differs: It gives the meaning of coprimality for an arbitrary pair of naturals and never asserts that the particular pair 9 and 28 has gcd one.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
3fb474a1bbe1 · pair key 9554f68f92f7.
Sign in to tag this passage
-
Example · supporting · Overview › A geometric view
✕Not formalized
For example, a 24-by-60 rectangular area can be divided into a grid of: 1-by-1 squares, 2-by-2 squares, 3-by-3 squares, 4-by-4 squares, 6-by-6 squares or 12-by-12 squares.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt 41a528375468). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · supporting · Overview › A geometric view
✕Not formalized
Therefore, 12 is the greatest common divisor of 24 and 60.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt 980f201c6a65). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Related, but states something else
Nat.gcd_greatest related
theorem Nat.gcd_greatest {a b d : ℕ} : d ∣ a → d ∣ b → (∀ (e : ℕ), e ∣ a → e ∣ b → e ∣ d) → d = a.gcd b
Mathlib.Data.Nat.GCD.Basic · lines 35–37
How it differs: At 24, 60 and 12 it still demands that every common divisor of the two numbers divide 12, a quantified hypothesis that decidable arithmetic alone does not settle (PD8).
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
e90b54593570 · pair key 9e505a0dd9e8.
Sign in to tag this passage
-
Example · supporting · Overview › A geometric view
✕Not formalized
A 24-by-60 rectangular area can thus be divided into a grid of 12-by-12 squares, with two squares along one edge (24/12 = 2) and five squares along the other (60/12 = 5).
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 5 queries and 0 candidates examined (receipt b083aee6bd3f). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Related, but states something else
Nat.div_eq_of_eq_mul_left related
theorem Nat.div_eq_of_eq_mul_left {n m k : Nat} : 0 < n → m = k * n → m / n = k
Init.Data.Nat.Div.Basic · lines 455–456
How it differs: It yields the exact quotients the passage cites as its reason, while the conjuncts assert how many squares lie along each edge of the rectangle, which no declaration here expresses.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
d8ff4fc44125 · pair key c1b3454da07f.
Sign in to tag this passage
-
Theorem · main statement · Overview › A geometric view
✕Not formalized
More generally, an a-by-b rectangle can be covered with square tiles of side length c only if c is a common divisor of a and b.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt f674f2d39192). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Example · supporting · Applications › Reducing fractions
✕Not formalized
For example, gcd(42, 56) = 14, therefore
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt 5ec7811d2fe1). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Related, but states something else
Nat.gcd_mul_right related
theorem Nat.gcd_mul_right (m n k : Nat) : (m * n).gcd (k * n) = m.gcd k * n
Init.Data.Nat.Gcd · lines 144–145
How it differs: It pulls a factor shared by both arguments out of a gcd, so reaching the value fourteen from it still needs the separate fact that three and four share no factor.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
b98d944cf4a1 · pair key 694a7628f841.
Sign in to tag this passage
-
Example · supporting · Applications › Reducing fractions
✕Not formalized
For example, gcd(42, 56) = 14, therefore,
4256 = 3 ⋅ 144 ⋅ 14 = 34.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt aa660d200eaf). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Related, but states something else
mul_div_mul_right related
theorem mul_div_mul_right {G₀ : Type*} [GroupWithZero G₀] {c : G₀} (a b : G₀) : c ≠ 0 → a * c / (b * c) = a / b
Mathlib.Algebra.GroupWithZero.Units.Basic · lines 363–364
How it differs: It cancels a nonzero factor carried by both numerator and denominator; the passage asserts an equation between two numerals, which is arithmetic evaluation rather than this identity.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
49f91fac2067 · pair key 9669339753ad.
Nat.coprime_div_gcd_div_gcd related
theorem Nat.coprime_div_gcd_div_gcd {m n : Nat} : 0 < m.gcd n → (m / m.gcd n).Coprime (n / m.gcd n)
Init.Data.Nat.Coprime · lines 63–65
How it differs: It says that dividing two numbers by their gcd leaves them with no shared factor, which is why reduction terminates, not what these two numerals reduce to.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
58d551543734 · pair key 0e856e53d946.
Sign in to tag this passage
-
Theorem · main statement · Applications › Least common multiple
✓Formalized
Formalized: Lean core states this up to a convention difference (proved).
The least common multiple of two integers that are not both zero can be computed from their greatest common divisor, by using the relation lcm(a, b) = |a ⋅ b|gcd(a, b).
Show in article · Read it in context on Wikipedia ↗
Int.lcm_eq_mul_div close match
theorem Int.lcm_eq_mul_div (m n : Int) : m.lcm n = m.natAbs * n.natAbs / m.gcd n
Init.Data.Int.Gcd · lines 447–448
Why close, not exact: Lean returns both the gcd and the lcm of integers as natural numbers and writes the absolute value of the product as the product of the two natAbs factors, with division taken in the naturals, where it is exact whenever the two integers are not both zero.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
091c93e2de13 · pair key 99dee4ffe480.
Nat.lcm_eq_mul_div special case
theorem Nat.lcm_eq_mul_div (m n : Nat) : m.lcm n = m * n / m.gcd n
Init.Data.Nat.Lcm · line 36
Why a special case: Both binders are ℕ, so it reaches the passage only at nonnegative arguments, where the absolute values may be dropped.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
e702528bbb82 · pair key 14376501afad.
Related, but states something else
Int.gcd_mul_lcm related
theorem Int.gcd_mul_lcm (m n : Int) : m.gcd n * m.lcm n = m.natAbs * n.natAbs
Init.Data.Int.Gcd · lines 450–451
How it differs: It states the product form, that the gcd times the lcm is the product of the absolute values; turning that into the passage's quotient needs a cancellation lemma for a nonzero gcd.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
f7ca8a373e83 · pair key f62bf26f3785.
Sign in to tag this passage
-
Example · supporting · Calculation › Using prime factorizations
✕Not formalized
For example, to compute gcd(48, 180), we find the prime factorizations 48 = 24 · 31 and 180 = 22 · 32 · 51; the GCD is then 2min(4,2) · 3min(1,2) · 5min(0,1) = 22 · 31 · 50 = 12 The corresponding LCM is then 2max(4,2) · 3max(1,2) · 5max(0,1) = 24 · 32 · 51 = 720.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt 3e7605246ef4). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Related, but states something else
Nat.prod_factorization_pow_eq_self related
theorem Nat.prod_factorization_pow_eq_self {n : ℕ} : n ≠ 0 → (n.factorization.prod fun x1 x2 ↦ x1 ^ x2) = n
Mathlib.Data.Nat.Factorization.Defs · lines 97–100
How it differs: It says that a nonzero natural number is the product of the prime powers recorded in its own factorization, and it fixes no exponent for either of the two numbers the passage factors.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
90dabe992248 · pair key 5e1d84354ff7.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Using prime factorizations
✕Not formalized
For example, to compute gcd(48, 180), we find the prime factorizations 48 = 24 · 31 and 180 = 22 · 32 · 51; the GCD is then 2min(4,2) · 3min(1,2) · 5min(0,1) = 22 · 31 · 50 = 12 The corresponding LCM is then 2max(4,2) · 3max(1,2) · 5max(0,1) = 24 · 32 · 51 = 720.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt 72725cf37333). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Related, but states something else
Nat.factorization_gcd related
theorem Nat.factorization_gcd {a b : ℕ} : a ≠ 0 → b ≠ 0 → (a.gcd b).factorization = a.factorization ⊓ b.factorization
Mathlib.Data.Nat.Factorization.Basic · lines 355–368
How it differs: It states that the factorization of a gcd of two nonzero numbers is the pointwise minimum of their factorizations; getting the value twelve from it still requires computing both factorizations and their product.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
e3932089543c · pair key 6a31c5643a1c.
TauCeti.Nat.gcd_eq_gcd_ordCompl_mul_pow_min related
theorem TauCeti.Nat.gcd_eq_gcd_ordCompl_mul_pow_min {p m n : ℕ} : Nat.Prime p → m ≠ 0 → n ≠ 0 → m.gcd n = (m / p ^ m.factorization p).gcd (n / p ^ n.factorization p) * p ^ Min.min (m.factorization p) (n.factorization p)
TauCeti.Data.Nat.Factorization.GcdSplit · lines 62–71
How it differs: It splits off one prime at a time, giving the gcd as a gcd of prime complements times that prime to the minimum exponent, and it never reaches a numerical value.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
83245ab. - Location key
ed2af1893baf · pair key 23b1e59a3de0.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Using prime factorizations
✕Not formalized
For example, to compute gcd(48, 180), we find the prime factorizations 48 = 24 · 31 and 180 = 22 · 32 · 51; the GCD is then 2min(4,2) · 3min(1,2) · 5min(0,1) = 22 · 31 · 50 = 12 The corresponding LCM is then 2max(4,2) · 3max(1,2) · 5max(0,1) = 24 · 32 · 51 = 720.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt fec22934a215). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Related, but states something else
Nat.factorization_lcm related
theorem Nat.factorization_lcm {a b : ℕ} : a ≠ 0 → b ≠ 0 → (a.lcm b).factorization = a.factorization ⊔ b.factorization
Mathlib.Data.Nat.Factorization.Basic · lines 370–376
How it differs: It states that the factorization of a least common multiple of two nonzero numbers is the pointwise maximum of their factorizations, and it stops short of any numerical value.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
2979543b8eee · pair key 6d65c7039dab.
Nat.lcm_eq_mul_div related
theorem Nat.lcm_eq_mul_div (m n : Nat) : m.lcm n = m * n / m.gcd n
Init.Data.Nat.Lcm · line 36
How it differs: It gives the least common multiple as the product divided by the gcd, which is another route to the example's number but not an assertion about these two arguments.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
441db54e3329 · pair key 4ae7b568af45.
Sign in to tag this passage
-
Theorem · main statement · Calculation › Euclid's algorithm
✓Formalized
Formalized: Mathlib states a more general result (proved).
The method introduced by Euclid for computing greatest common divisors is based on the fact that, given two positive integers a and b such that a > b, the common divisors of a and b are the same as the common divisors of a – b and b.
Show in article · Read it in context on Wikipedia ↗
dvd_sub_left more general
theorem dvd_sub_left {α : Type*} [NonUnitalRing α] {a b c : α} : a ∣ c → (a ∣ b - c ↔ a ∣ b)
Mathlib.Algebra.Ring.Divisibility.Basic · lines 137–138
Why more general: It is stated for one divisor of b at a time and over any non-unital ring; the passage's two collections agree because divisibility of b is shared by both sides of the equivalence.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
37233a34fc63 · pair key 491f5a1bfa77.
Related, but states something else
Int.gcd_sub_self_left related
theorem Int.gcd_sub_self_left (m n : Int) : (n - m).gcd m = n.gcd m
Init.Data.Int.Gcd · lines 313–314
How it differs: It says the gcd is unchanged when one integer is subtracted from the other, which is an equation between two greatest common divisors rather than the agreement of the two collections of common divisors.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
dcb201f6b813 · pair key 81b52e33d0c4.
Sign in to tag this passage
-
Construction · main statement · Calculation › Euclid's algorithm
✕Not formalized
So, Euclid's method for computing the greatest common divisor of two positive integers consists of replacing the larger number with the difference of the numbers, and repeating this until the two numbers are equal: that is their greatest common divisor.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 0 candidates examined (receipt b3faf01eef7e). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Related, but states something else
Nat.gcd related
def Nat.gcd : Nat → Nat → Nat
Init.Data.Nat.Gcd · lines 35–41
How it differs: Lean's gcd on naturals recurses on the remainder of a division rather than on the difference of the two numbers, so it is a different construction that happens to take the same values.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
c31de81c5226 · pair key c7680c564ba0.
Nat.gcd_sub_self_left related
theorem Nat.gcd_sub_self_left {m n : Nat} : m ≤ n → (n - m).gcd m = n.gcd m
Init.Data.Nat.Gcd · lines 329–330
How it differs: It states that one subtraction step leaves the gcd unchanged, and says nothing about iterating the step, about stopping when the two numbers agree, or about the value then reached.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
327478679d3a · pair key 3bbc7a6798c8.
Sign in to tag this passage
-
Example · supporting · Calculation › Euclid's algorithm
✓Formalized
Formalized: Lean core states a more general result (proved).
For example, to compute gcd(48,18), one proceeds as follows: gcd(48, 18)→ gcd(48 − 18, 18) = gcd(30, 18)→ gcd(30 − 18, 18) = gcd(12, 18)→ gcd(12, 18 − 12) = gcd(12, 6)→ gcd(12 − 6, 6) = gcd(6, 6).
Show in article · Read it in context on Wikipedia ↗
Nat.gcd_sub_self_left more general
theorem Nat.gcd_sub_self_left {m n : Nat} : m ≤ n → (n - m).gcd m = n.gcd m
Init.Data.Nat.Gcd · lines 329–330
Why more general: Lean states for naturals that subtracting the smaller number from the larger leaves the pair's gcd unchanged, which is the law each step of this computation uses.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
e3749554800e · pair key 00e70eb42423.
Nat.gcd_sub_self_right more general
theorem Nat.gcd_sub_self_right {m n : Nat} : m ≤ n → m.gcd (n - m) = m.gcd n
Init.Data.Nat.Gcd · lines 323–324
Why more general: The companion lemma subtracts the first entry from the second and keeps the gcd, which is the step that turns the pair twelve and eighteen into twelve and six.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
1a04962d8eb9 · pair key c563daefe441.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Euclid's algorithm
✕Not formalized
So gcd(48, 18) = 6.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt 3deab2c6ccf0). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Construction · main statement · Calculation › Euclidean algorithm
✓Formalized
Formalized: Lean core states this up to a convention difference (a definition).
A more efficient method is the Euclidean algorithm, a variant in which the difference of the two numbers a and b is replaced by the remainder of the Euclidean division (also called division with remainder) of a by b.
Show in article · Read it in context on Wikipedia ↗
Nat.gcd close match
def Nat.gcd : Nat → Nat → Nat
Init.Data.Nat.Gcd · lines 35–41
Why close, not exact: Lean defines this function by the recursion that divides one argument by the other and keeps the remainder, taking the pair in the order with the divisor second and stopping once the first entry is zero.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
0d0425de5a07 · pair key f5a86da64e4a.
EuclideanDomain.gcd more general
def EuclideanDomain.gcd {R : Type u} [EuclideanDomain R] [DecidableEq R] : R → R → R
Mathlib.Algebra.EuclideanDomain.Defs · lines 180–185
Why more general: Mathlib builds the same remainder recursion for every ring with Euclidean division, so the passage's integers are one instance of its setting.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
f811c21ac3a2 · pair key be0ee4204321.
Nat.gcd_rec states part
theorem Nat.gcd_rec (m n : Nat) : m.gcd n = (n % m).gcd m
Init.Data.Nat.Gcd · lines 74–77
Why only part: The lemma records the remainder step of the recursion as an equation between gcd values, without naming the method as a whole.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
177abdc4cdd7 · pair key b0d992eb2365.
Sign in to tag this passage
-
Construction · main statement · Calculation › Euclidean algorithm
✓Formalized
Formalized: Lean core states this up to a convention difference (a definition).
Denoting this remainder as a mod b, the algorithm replaces (a, b) with (b, a mod b) repeatedly until the pair is (d, 0), where d is the greatest common divisor.
Show in article · Read it in context on Wikipedia ↗
Nat.gcd close match
def Nat.gcd : Nat → Nat → Nat
Init.Data.Nat.Gcd · lines 35–41
Why close, not exact: Lean's recursion carries the pair with the divisor in second position, recurses on the remainder of the second entry by the first, and returns the second entry as soon as the first is zero.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
f5b3f996c589 · pair key bbd6636c2723.
EuclideanDomain.gcd more general
def EuclideanDomain.gcd {R : Type u} [EuclideanDomain R] [DecidableEq R] : R → R → R
Mathlib.Algebra.EuclideanDomain.Defs · lines 180–185
Why more general: Mathlib's construction performs the same loop in any ring with Euclidean division, with the zero entry ending the recursion.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
fe95fa5ca777 · pair key 23cb7c5cfd38.
Nat.gcd_rec states part
theorem Nat.gcd_rec (m n : Nat) : m.gcd n = (n % m).gcd m
Init.Data.Nat.Gcd · lines 74–77
Why only part: The lemma states the loop's single step as an equation, leaving the stopping condition to other declarations.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
a409b72d3353 · pair key 4ff8aa29f951.
Nat.gcd_zero_right states part
theorem Nat.gcd_zero_right (n : Nat) : n.gcd 0 = n
Init.Data.Nat.Gcd · lines 59–65
Why only part: The lemma gives the value at the terminating pair, which is where the passage stops the loop.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 4 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
6177f2688ff0 · pair key 779abe5e1c72.
Sign in to tag this passage
-
Example · supporting · Calculation › Euclidean algorithm
✓Formalized
Formalized: Lean core states a more general result (proved).
For example, to compute gcd(48,18), the computation is as follows: gcd(48, 18)→ gcd(18, 48mod18) = gcd(18, 12)→ gcd(12, 18mod12) = gcd(12, 6)→ gcd(6, 12mod6) = gcd(6, 0).
Show in article · Read it in context on Wikipedia ↗
Nat.gcd_rec more general
theorem Nat.gcd_rec (m n : Nat) : m.gcd n = (n % m).gcd m
Init.Data.Nat.Gcd · lines 74–77
Why more general: Lean states the remainder step for arbitrary naturals, with the remainder taken of the second argument by the first, which the example performs at the numbers forty eight and eighteen.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
f8d34445f705 · pair key 4f9af9205693.
Nat.gcd_succ more general
theorem Nat.gcd_succ (x y : Nat) : x.succ.gcd y = (y % x.succ).gcd x.succ
Init.Data.Nat.Gcd · lines 46–47
Why more general: This form of the recursion is written for a nonzero first argument, which is the situation at every step of the computation before the last.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
d367cf2d3ed1 · pair key 0b31a474e083.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Euclidean algorithm
✕Not formalized
This again gives gcd(48, 18) = 6.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt c6162ad2edbf). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Construction · supporting · Calculation › Binary GCD algorithm
✕Not formalized
If a and b are both even, then divide both by two until at least one of them becomes odd; let d be the number of these paired divisions.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt 6a35517a77bb). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Construction · supporting · Calculation › Binary GCD algorithm
✓Formalized
Formalized: Mathlib states a more general result (a definition).
If a is even, then divide it by two until it becomes odd.
Show in article · Read it in context on Wikipedia ↗
Nat.divMaxPow more general
def Nat.divMaxPow : ℕ → ℕ → ℕ
Mathlib.Data.Nat.MaxPowDiv · line 54
Why more general: Mathlib defines this as the quotient of a number by the largest power of the base dividing it, and at base two that quotient is the odd number the passage's halving reaches.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
d2992c34ef8c · pair key eed2e82503bd.
Nat.maxPowDvdDiv more general
def Nat.maxPowDvdDiv : ℕ → ℕ → ℕ × ℕ
Mathlib.Data.Nat.MaxPowDiv · lines 32–51
Why more general: This construction returns both how many times the base divides the number and the quotient that remains, the latter being the odd number the passage's halving produces.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
33ba31c17752 · pair key 913dcad04ec1.
Sign in to tag this passage
-
Construction · supporting · Calculation › Binary GCD algorithm
✓Formalized
Formalized: Mathlib states a more general result (a definition).
If b is even, then divide it by two until it becomes odd.
Show in article · Read it in context on Wikipedia ↗
Nat.divMaxPow more general
def Nat.divMaxPow : ℕ → ℕ → ℕ
Mathlib.Data.Nat.MaxPowDiv · line 54
Why more general: Mathlib divides a number by the largest power of an arbitrary base dividing it, and the passage uses the base two.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
267548637b3c · pair key 496afda6f3f8.
Nat.maxPowDvdDiv more general
def Nat.maxPowDvdDiv : ℕ → ℕ → ℕ × ℕ
Mathlib.Data.Nat.MaxPowDiv · lines 32–51
Why more general: It returns both the number of divisions performed and the quotient, where the passage keeps only the quotient.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
7995b201f010 · pair key 3637e589de74.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Binary GCD algorithm
◔Partial
Partial: Mathlib states part of this (proved).
Now, a and b are both odd and will remain odd until the end of the computation
Show in article · Read it in context on Wikipedia ↗
Nat.exists_eq_two_pow_mul_odd states part
theorem Nat.exists_eq_two_pow_mul_odd {n : ℕ} : n ≠ 0 → ∃ k m, Odd m ∧ n = 2 ^ k * m
Mathlib.Data.Nat.Factorization.Basic · lines 282–285
Why only part: It fixes the oddness reached by the halving steps, and says nothing about the later loop keeping the two numbers odd.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
a95757787bad · pair key df4538e5b688.
Nat.not_dvd_divMaxPow states part
theorem Nat.not_dvd_divMaxPow {p n : ℕ} : 1 < p → n ≠ 0 → ¬p ∣ n.divMaxPow p
Mathlib.Data.Nat.MaxPowDiv · lines 95–96
Why only part: It pins the result of a halving as odd whenever one is performed, but does not model the algorithm's later iterations.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
de04c7b47f14 · pair key 732f56b977c9.
Sign in to tag this passage
-
Construction · supporting · Calculation › Binary GCD algorithm
◔Partial
Partial: Mathlib states part of this (proved).
While a ≠ b do If a > b, then replace a with a – b and divide the result by two until a becomes odd (as a and b are both odd, there is, at least, one division by 2).
Show in article · Read it in context on Wikipedia ↗
Nat.Odd.sub_odd states part
theorem Nat.Odd.sub_odd {m n : ℕ} : Odd m → Odd n → Even (m - n)
Mathlib.Algebra.Ring.Parity · line 297
Why only part: It yields the guarantee of a division by two attached to this step, not the replacement of a by the halved difference.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
46f6ee70cf43 · pair key d79691d3a622.
Nat.divMaxPow states part
def Nat.divMaxPow : ℕ → ℕ → ℕ
Mathlib.Data.Nat.MaxPowDiv · line 54
Why only part: It supplies the halving half of the step; the branch test and the guarantee of one division come from elsewhere.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
5e71db768de8 · pair key 5d86b00da4c8.
Related, but states something else
Nat.gcd_sub_self_left related
theorem Nat.gcd_sub_self_left {m n : Nat} : m ≤ n → (n - m).gcd m = n.gcd m
Init.Data.Nat.Gcd · lines 329–330
How it differs: Replacing the larger number by the difference leaves the gcd alone; the passage prescribes the replacement rather than asserting its correctness.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
c4221970c9dd · pair key 951a8d63da2b.
Sign in to tag this passage
-
Construction · supporting · Calculation › Binary GCD algorithm
✓Formalized
Formalized: Mathlib states a more general result (a definition).
If a < b, then replace b with b – a and divide the result by two until b becomes odd.
Show in article · Read it in context on Wikipedia ↗
Nat.divMaxPow more general
def Nat.divMaxPow : ℕ → ℕ → ℕ
Mathlib.Data.Nat.MaxPowDiv · line 54
Why more general: Mathlib removes the largest power of an arbitrary base, and the passage applies the base two to the difference it has just formed.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
34ff3608e043 · pair key 749dad437dc7.
Related, but states something else
Nat.gcd_sub_self_right related
theorem Nat.gcd_sub_self_right {m n : Nat} : m ≤ n → m.gcd (n - m) = m.gcd n
Init.Data.Nat.Gcd · lines 323–324
How it differs: Subtracting the smaller number from the larger leaves the gcd unchanged, which is a fact about gcd rather than this replacement step.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
fe8903331011 · pair key 8777c3545cd4.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Binary GCD algorithm
✕Not formalized
Now, a = b, and the greatest common divisor is 2da.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt 5e8fb4debaa8). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · main statement · Calculation › Binary GCD algorithm
◔Partial
Partial: TauCeti states part of this (proved).
Now, a = b, and the greatest common divisor is 2da.
Show in article · Read it in context on Wikipedia ↗
TauCeti.Nat.gcd_eq_gcd_ordCompl_mul_pow_min states part
theorem TauCeti.Nat.gcd_eq_gcd_ordCompl_mul_pow_min {p m n : ℕ} : Nat.Prime p → m ≠ 0 → n ≠ 0 → m.gcd n = (m / p ^ m.factorization p).gcd (n / p ^ n.factorization p) * p ^ Min.min (m.factorization p) (n.factorization p)
TauCeti.Data.Nat.Factorization.GcdSplit · lines 62–71
Why only part: It accounts for the factor two to the d and leaves unstated that the value the iteration ends on is the gcd of the odd parts.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
83245ab. - Location key
59d4b76326e7 · pair key cf2da5e8d5cc.
Related, but states something else
Nat.gcd_mul_left related
theorem Nat.gcd_mul_left (m n k : Nat) : (m * n).gcd (m * k) = m * n.gcd k
Init.Data.Nat.Gcd · lines 139–142
How it differs: It pulls a shared factor out of a gcd, with no mention of the paired halvings or of the value the iteration ends on.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
d472f5e7e7a8 · pair key e03442731be5.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Binary GCD algorithm
✓Formalized
Formalized: Mathlib states a more general result (proved).
Step 1 determines d as the highest power of 2 that divides a and b, and thus their greatest common divisor.
Show in article · Read it in context on Wikipedia ↗
Nat.factorization_gcd more general
theorem Nat.factorization_gcd {a b : ℕ} : a ≠ 0 → b ≠ 0 → (a.gcd b).factorization = a.factorization ⊓ b.factorization
Mathlib.Data.Nat.Factorization.Basic · lines 355–368
Why more general: Mathlib records the exponents of every prime at once, and the passage reads the entry at two.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
529f55f73b95 · pair key 6db2491f4f6b.
TauCeti.Nat.gcd_eq_gcd_ordCompl_mul_pow_min states part
theorem TauCeti.Nat.gcd_eq_gcd_ordCompl_mul_pow_min {p m n : ℕ} : Nat.Prime p → m ≠ 0 → n ≠ 0 → m.gcd n = (m / p ^ m.factorization p).gcd (n / p ^ n.factorization p) * p ^ Min.min (m.factorization p) (n.factorization p)
TauCeti.Data.Nat.Factorization.GcdSplit · lines 62–71
Why only part: It displays the power of two inside the gcd without naming it as the full exponent of two there.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
83245ab. - Location key
7c2c46dd4dcd · pair key e9bc2a4b1b25.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Binary GCD algorithm
✕Not formalized
None of the steps changes the set of the odd common divisors of a and b.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt 2f66090d7995). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · main statement · Calculation › Binary GCD algorithm
✕Not formalized
This shows that when the algorithm stops, the result is correct.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 81f5d7488d48). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Binary GCD algorithm
✕Not formalized
The algorithm stops eventually, since each steps divides at least one of the operands by at least 2.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 1 candidates examined (receipt 0c9ed68ce476). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · supporting · Calculation › Binary GCD algorithm
✕Not formalized
The algorithm stops eventually, since each steps divides at least one of the operands by at least 2.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 1 candidates examined (receipt e4d3de8353bf). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Binary GCD algorithm
✕Not formalized
Moreover, the number of divisions by 2 and thus the number of subtractions is at most the total number of digits.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt ac44c12c98d4). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Example · supporting · Calculation › Binary GCD algorithm
✕Not formalized
Example: (a, b, d) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1) ; the original GCD is thus the product 6 of 2d = 21 and a = b = 3.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 0 candidates examined (receipt 39d634d1d73d). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · supporting · Calculation › Binary GCD algorithm
◔Partial
With community edits: Partial. As published it is Formalized.
Partial, by a community edit: Lean core states part of this (proved).
Example: (a, b, d) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1) ; the original GCD is thus the product 6 of 2d = 21 and a = b = 3.
Show in article · Read it in context on Wikipedia ↗
Nat.gcd_mul_left states part
theorem Nat.gcd_mul_left (m n k : Nat) : (m * n).gcd (m * k) = m * n.gcd k
Init.Data.Nat.Gcd · lines 139–142
Community Agent The pipeline said more general; changed by Meta FAIR 2 (agent) — owned by Jack McCarthy on 9 Nov 2026.
Why only part: Nat.gcd_mul_left says gcd(m*n, m*k) = m * gcd(n, k). Taking m = 2^d pulls the common power of two out of the gcd, the factor the passage writes as 2^d = 2^1. It does not show that the remaining gcd equals the final a = b = 3 of the algorithm, so it states only the factoring part of the claim that the original gcd is the product 6.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
00bd56547d87 · pair key 2373fbf07f02.
Sign in to tag this passage
-
Theorem · main statement · Calculation › Binary GCD algorithm
✕Not formalized
Its computational complexity is O((log a + log b)2).
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 29371dece000). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Binary GCD algorithm
✕Not formalized
The square in this complexity comes from the fact that division by 2 and subtraction take a time that is proportional to the number of bits of the input.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 1 candidates examined (receipt f769e6b117c8). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Notation · supporting · Calculation › Binary GCD algorithm
✕Not formalized
Here, this length is n = log a + log b, and the complexity is thus
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 0 candidates examined (receipt 4bfee0dd5221). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · main statement · Calculation › Binary GCD algorithm
✕Not formalized
Here, this length is n = log a + log b, and the complexity is thus O(n2).
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 1 candidates examined (receipt faaa586a7ec1). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · main statement · Calculation › Lehmer's GCD algorithm
✕Not formalized
Lehmer's algorithm is based on the observation that the initial quotients produced by Euclid's algorithm can be determined based on only the first few digits; this is useful for numbers that are larger than a computer word.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt 51311e7d2100). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · main statement · Calculation › Other methods
✓Formalized
Formalized: Lean core states this up to a convention difference (proved).
If a and b are both nonzero, the greatest common divisor of a and b can be computed by using least common multiple (LCM) of a and b: gcd(a, b) = |a ⋅ b|lcm(a, b), but more commonly the LCM is computed from the GCD.
Show in article · Read it in context on Wikipedia ↗
Int.gcd_mul_lcm close match
theorem Int.gcd_mul_lcm (m n : Int) : m.gcd n * m.lcm n = m.natAbs * n.natAbs
Init.Data.Int.Gcd · lines 450–451
Why close, not exact: Lean clears the denominator, equating the product of gcd and lcm with the product of the two absolute values, which is how a library states it when integer division truncates; the extra zero cases read 0 = 0.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
4e16ff10f6f8 · pair key 3138189ab879.
Nat.gcd_mul_lcm special case
theorem Nat.gcd_mul_lcm (m n : Nat) : m.gcd n * m.lcm n = m * n
Init.Data.Nat.Lcm · lines 38–40
Why a special case: The statement lives over ℕ, so it covers the positive inputs of the sentence and reaches negative ones only through their absolute values.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
649600eb4800 · pair key adc7d5abb6ed.
Sign in to tag this passage
-
Theorem · main statement · Calculation › Other methods
✕Not formalized
Using Thomae's function f, gcd(a, b) = af(ba), which generalizes to a and b rational numbers or commensurable real numbers.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt f5ed5151a205). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Related, but states something else
Rat.den_divInt related
theorem Rat.den_divInt (a b : Int) : (Rat.divInt a b).den = if b = 0 then 1 else b.natAbs / b.gcd a
Init.Data.Rat.Lemmas · lines 230–238
How it differs: It computes the reduced denominator of a quotient of two integers, and that denominator is the reciprocal of the value Thomae's function takes there.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
67217aeab933 · pair key 4b618dd37e0c.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Other methods
✕Not formalized
Keith Slavin has shown that for odd a ≥ 1: gcd(a, b) = log2 ∏a − 1k = 0(1 + e−2iπkb/a) which is a function that can be evaluated for complex b.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 0 candidates examined (receipt ae6bff787db8). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Other methods
✕Not formalized
Wolfgang Schramm has shown that gcd(a, b) = ∑ak = 1 exp(2πikb/a) ⋅ ∑d|a cd(k)d is an entire function in the variable b for all positive integers a where cd(k) is Ramanujan's sum.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 1 candidates examined (receipt 261bd991cdf4). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · main statement · Calculation › Complexity
✕Not formalized
If one uses the Euclidean algorithm and the elementary algorithms for multiplication and division, the computation of the greatest common divisor of two integers of at most n bits is O(n2).[citation needed] This means that the computation of greatest common divisor has, up to a constant factor, the same complexity as the multiplication.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt 8bbd63c2bf06). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Complexity
✕Not formalized
If one uses the Euclidean algorithm and the elementary algorithms for multiplication and division, the computation of the greatest common divisor of two integers of at most n bits is O(n2).[citation needed] This means that the computation of greatest common divisor has, up to a constant factor, the same complexity as the multiplication.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt f5ecb8d1f957). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · main statement · Calculation › Complexity
✕Not formalized
More precisely, if the multiplication of two integers of n bits takes a time of T(n), then the fastest known algorithm for greatest common divisor has a complexity O(T(n) log n).
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt c8ca4f144334). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Complexity
✕Not formalized
This implies that the fastest known algorithm has a complexity of O(n (log n)2).
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 514cf00e6675). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · main statement · Calculation › Complexity
✕Not formalized
The computation of the greatest common divisors belongs thus to the class of problems solvable in quasilinear time.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt b80b7e381cb4). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Complexity
✕Not formalized
A fortiori, the corresponding decision problem belongs to the class P of problems solvable in polynomial time.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt f152aba1a343). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Complexity
✕Not formalized
Shallcross et al. showed that a related problem (EUGCD, determining the remainder sequence arising during the Euclidean algorithm) is NC-equivalent to the problem of integer linear programming with two variables; if either problem is in NC or is P-complete, the other is as well.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 37d221d14568). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Complexity
✕Not formalized
Shallcross et al. showed that a related problem (EUGCD, determining the remainder sequence arising during the Euclidean algorithm) is NC-equivalent to the problem of integer linear programming with two variables; if either problem is in NC or is P-complete, the other is as well.[19]
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 4b9e4a4b8b5a). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · supporting · Calculation › Complexity
✕Not formalized
Since NC contains NL, it is also unknown whether a space-efficient algorithm for computing the GCD exists, even for nondeterministic Turing machines.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt 4a80b3c8d109). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · main statement · Calculation › Complexity
✕Not formalized
Although the problem is not known to be in NC, parallel algorithms asymptotically faster than the Euclidean algorithm exist; the fastest known deterministic algorithm is by Chor and Goldreich, which (in the CRCW-PRAM model) can solve the problem in O(n/log n) time with n1+ε processors.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt 52643404b9b5). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · Calculation › Complexity
✕Not formalized
Although the problem is not known to be in NC, parallel algorithms asymptotically faster than the Euclidean algorithm exist; the fastest known deterministic algorithm is by Chor and Goldreich, which (in the CRCW-PRAM model) can solve the problem in O(n/log n) time with n1+ε processors.[20]
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt 2bd9745b4087). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · supporting · Calculation › Complexity
✕Not formalized
Randomized algorithms can solve the problem in O((log n)2) time on O(e√nlog n) processors (this is superpolynomial).
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt ab2f4f1576e0). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Lean core states a more general result (proved).
For every positive integer a, gcd(a, a) = a.
Show in article · Read it in context on Wikipedia ↗
Int.gcd_self more general
theorem Int.gcd_self {a : Int} : a.gcd a = a.natAbs
Init.Data.Int.Gcd · line 67
Why more general: Lean's Int.gcd takes values in ℕ and writes the answer as natAbs, the natural-number absolute value; the lemma is stated for every integer, not only the positive ones the passage names.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
361bbd36ed38 · pair key 8c19d67b9ee9.
Nat.gcd_self more general
theorem Nat.gcd_self (n : Nat) : n.gcd n = n
Init.Data.Nat.Gcd · lines 70–71
Why more general: The binder here is ℕ rather than ℤ, so the lemma speaks of natural numbers; the passage quantifies only over positive integers, which are exactly the nonzero naturals under the usual inclusion, and Nat.gcd agrees there with the article's gcd, so the passage is fully stated.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
d6cff101114c · pair key 8e987f3112bb.
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Mathlib states a more general result (proved).
Every common divisor of a and b is a divisor of gcd(a, b).
Show in article · Read it in context on Wikipedia ↗
dvd_gcd_iff more general
theorem dvd_gcd_iff {α : Type*} [CommMonoidWithZero α] [GCDMonoid α] (a b c : α) : a ∣ GCDMonoid.gcd b c ↔ a ∣ b ∧ a ∣ c
Mathlib.Algebra.GCDMonoid.Basic · lines 385–387
Why more general: Mathlib proves the two-way version, so divisibility of the gcd is characterised rather than merely implied, and it does so for any gcd monoid rather than for ℤ alone.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
3d64ee78300b · pair key 0718a6abbf57.
Int.dvd_gcd special case
theorem Int.dvd_gcd {a b : Int} {c : Nat} : ↑c ∣ a → ↑c ∣ b → c ∣ a.gcd b
Init.Data.Int.Gcd · lines 93–94
Why a special case: The divisor slot is ℕ rather than ℤ, so the statement covers the nonnegative common divisors only; reaching a negative divisor needs Int.natAbs_dvd on top of it.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
fc8a6bb8b2c8 · pair key 77e67efc67ab.
Nat.dvd_gcd special case
theorem Nat.dvd_gcd {k m n : Nat} : k ∣ m → k ∣ n → k ∣ m.gcd n
Init.Data.Nat.Gcd · lines 100–103
Why a special case: Every binder is ℕ, so this is the article's property restricted to natural numbers, where the passage ranges over integers.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
6aeb2f57d4ce · pair key 85fdb73d71a9.
Sign in to tag this passage
-
Theorem · main statement · Properties
◔Partial
Partial: Mathlib states a special case (proved).
gcd(a, b), where a and b are not both zero, may be defined alternatively and equivalently as the smallest positive integer d which can be written in the form d = a⋅p + b⋅q, where p and q are integers.
Show in article · Read it in context on Wikipedia ↗
Int.gcd_least_linear special case
theorem Int.gcd_least_linear {a b : ℤ} : a ≠ 0 → IsLeast {n | 0 < n ∧ ∃ x y, ↑n = a * x + b * y} (a.gcd b)
Mathlib.Data.Int.GCD · lines 249–255
Why a special case: Mathlib writes the candidate set over ℕ, with positivity as 0 < n and Int.gcd returning a natural number, while the coefficients x and y stay in ℤ; the article's docstring-level reading and this one agree once that ℕ-valued packaging is unwound.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack, which downgraded it. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
35e133f5ad54 · pair key 1df57e4e1762.
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Lean core states a more general result (proved).
gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the greatest divisor of a is |a|.
Show in article · Read it in context on Wikipedia ↗
Int.gcd_zero_right more general
theorem Int.gcd_zero_right (a : Int) : a.gcd 0 = a.natAbs
Init.Data.Int.Gcd · line 65
Why more general: Lean's Int.gcd is ℕ-valued and the right-hand side is natAbs, the natural-number absolute value; the lemma drops the article's restriction to nonzero a and keeps the equation at a = 0 as well.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
49ba3b0ef9a7 · pair key 9278aea37232.
Nat.gcd_zero_right special case
theorem Nat.gcd_zero_right (n : Nat) : n.gcd 0 = n
Init.Data.Nat.Gcd · lines 59–65
Why a special case: The binder is ℕ, so negative a is outside its reach altogether, and the absolute value on the right collapses to the argument.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
957813f25d76 · pair key f680610ff507.
Sign in to tag this passage
-
Theorem · supporting · Properties
✓Formalized
Formalized: Lean core states this exactly (proved).
gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the greatest divisor of a is |a|.
Show in article · Read it in context on Wikipedia ↗
Int.dvd_zero exact match
theorem Int.dvd_zero (n : Int) : n ∣ 0
Init.Data.Int.DivMod.Bootstrap · line 31
Note: Both the passage and this declaration quantify over all of the integers.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
c2d2063d4705 · pair key 5cd05b8a5ae2.
dvd_zero more general
theorem dvd_zero {α : Type*} [SemigroupWithZero α] (a : α) : a ∣ 0
Mathlib.Algebra.GroupWithZero.Divisibility · lines 43–44
Why more general: It is stated for any semigroup with a zero element, the integers being one such.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
eed2e21becdf · pair key 1b2426290740.
Sign in to tag this passage
-
Theorem · supporting · Properties
◔Partial
Partial: Lean core states part of this (proved).
gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the greatest divisor of a is |a|.[2][5]
Show in article · Read it in context on Wikipedia ↗
Int.natAbs_dvd_self states part
theorem Int.natAbs_dvd_self {a : Int} : ↑a.natAbs ∣ a
Init.Data.Int.DivMod.Lemmas · lines 96–98
Why only part: Lean writes the absolute value as the cast of natAbs back to the integers.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
75d8e1cd03f6 · pair key a3c0eecf0f35.
Int.le_abs_of_dvd states part
theorem Int.le_abs_of_dvd {a b : ℤ} : b ≠ 0 → a ∣ b → a ≤ |b|
Mathlib.Algebra.Order.Ring.Abs · lines 282–283
Why only part: It bounds each divisor of a nonzero integer by that integer's absolute value.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC). - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
f599a02de555 · pair key 10fd3dca4590.
Sign in to tag this passage
-
Theorem · main statement · Properties
◔Partial
Partial: Mathlib states a special case (proved).
If a divides the product b⋅c, and gcd(a, b) = d, then a/d divides c.
Show in article · Read it in context on Wikipedia ↗
Int.dvd_of_dvd_mul_right_of_gcd_one special case
theorem Int.dvd_of_dvd_mul_right_of_gcd_one {a b c : ℤ} : a ∣ b * c → a.gcd b = 1 → a ∣ c
Mathlib.Data.Int.GCD · lines 242–245
Why a special case: Euclid's lemma, which is the passage read at d equal to one, where the quotient a/d is a itself.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
88c281d41212 · pair key 6727d53c694f.
IsCoprime.dvd_of_dvd_mul_left special case
theorem IsCoprime.dvd_of_dvd_mul_left {R : Type u} [CommSemiring R] {x y z : R} : IsCoprime x y → x ∣ y * z → x ∣ z
Mathlib.RingTheory.Coprime.Basic · lines 103–106
Why a special case: Coprimality here is Mathlib's IsCoprime, which over the integers amounts to the gcd being one.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
c22fe8fac767 · pair key dd30849d6c80.
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Lean core states a more general result (proved).
If m is a positive integer, then gcd(m⋅a, m⋅b) = m⋅gcd(a, b).
Show in article · Read it in context on Wikipedia ↗
Int.gcd_mul_left more general
theorem Int.gcd_mul_left (m n k : Int) : (m * n).gcd (m * k) = m.natAbs * n.gcd k
Init.Data.Int.Gcd · lines 122–123
Why more general: It is stated for every integer multiplier, carrying the multiplier's absolute value on the right-hand side.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
7418d20f0d26 · pair key 207580f05ddd.
gcd_mul_left more general
theorem gcd_mul_left {α : Type*} [CommMonoidWithZero α] [StrongNormalizedGCDMonoid α] (a b c : α) : GCDMonoid.gcd (a * b) (a * c) = normalize a * GCDMonoid.gcd b c
Mathlib.Algebra.GCDMonoid.Basic · lines 490–501
Why more general: Stated over any such monoid, with normalize of the multiplier in place of the multiplier.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
8a6ec9f61ade · pair key fa61375899d6.
Nat.gcd_mul_left special case
theorem Nat.gcd_mul_left (m n k : Nat) : (m * n).gcd (m * k) = m * n.gcd k
Init.Data.Nat.Gcd · lines 139–142
Why a special case: Its binders are ℕ, so it reaches only the nonnegative instances of the passage; the multiplier zero makes both sides vanish.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
f40517bf5738 · pair key 0c4ee9b58dd5.
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Lean core states this exactly (proved).
If m is any integer, then gcd(a + m⋅b, b) = gcd(a, b).
Show in article · Read it in context on Wikipedia ↗
Int.gcd_add_mul_right_left exact match
theorem Int.gcd_add_mul_right_left (m n k : Int) : (n + k * m).gcd m = n.gcd m
Init.Data.Int.Gcd · lines 243–244
Note: Its multiplier ranges over all of the integers, exactly as the passage's m does.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
8c839a35ebd4 · pair key a81379e61cd1.
Nat.gcd_add_mul_right_left special case
theorem Nat.gcd_add_mul_right_left (m n k : Nat) : (n + k * m).gcd m = n.gcd m
Init.Data.Nat.Gcd · lines 251–252
Why a special case: Its binders are ℕ, so it covers the nonnegative instances of the passage only.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
c51c91dc9190 · pair key bc7d4bc4eec8.
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Mathlib states this exactly (proved).
Equivalently, gcd(a mod b,b) = gcd(a,b).
Show in article · Read it in context on Wikipedia ↗
Int.gcd_emod exact match
theorem Int.gcd_emod (m n : ℤ) : (m % n).gcd n = m.gcd n
Mathlib.Data.Int.Basic · lines 89–90
Note: Here % is Lean's remainder on the integers, which is the operation the passage writes as mod.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
ecde7f32a6b6 · pair key 3051e0687fb0.
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Mathlib states a more general result (proved).
If m is a positive common divisor of a and b, then gcd(a/m, b/m) = gcd(a, b)/m.
Show in article · Read it in context on Wikipedia ↗
Int.gcd_div more general
theorem Int.gcd_div {a b c : ℤ} : c ∣ a → c ∣ b → (a / c).gcd (b / c) = a.gcd b / c.natAbs
Mathlib.Data.Int.GCD · line 186
Why more general: Stated for any common divisor, negative ones included, with the divisor's absolute value on the right.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
05b4299c4997 · pair key f33b21ac4375.
Nat.gcd_div special case
theorem Nat.gcd_div {m n k : Nat} : k ∣ m → k ∣ n → (m / k).gcd (n / k) = m.gcd n / k
Init.Data.Nat.Gcd · lines 172–179
Why a special case: Its binders are ℕ, so it reaches the nonnegative instances of the passage; the divisor zero forces both arguments to vanish.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
8abba694f5ba · pair key 10eb02cbb299.
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Mathlib states this up to a convention difference (proved).
If gcd(a, b) = d, then gcd(a/d, b/d) = 1.
Show in article · Read it in context on Wikipedia ↗
Int.gcd_div_gcd_div_gcd close match
theorem Int.gcd_div_gcd_div_gcd {i j : ℤ} : 0 < i.gcd j → (i / ↑(i.gcd j)).gcd (j / ↑(i.gcd j)) = 1
Mathlib.Data.Int.GCD · line 187
Why close, not exact: Lean's integer gcd takes its values in ℕ and is cast back to the integers for the two divisions, and the conclusion is an equation of natural numbers.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
c2a3ae9b3c32 · pair key 3257fdb52633.
isCoprime_div_gcd_div_gcd_of_gcd_ne_zero more general
theorem isCoprime_div_gcd_div_gcd_of_gcd_ne_zero {R : Type*} [EuclideanDomain R] [GCDMonoid R] {p q : R} : GCDMonoid.gcd p q ≠ 0 → IsCoprime (p / GCDMonoid.gcd p q) (q / GCDMonoid.gcd p q)
Mathlib.RingTheory.EuclideanDomain · lines 57–62
Why more general: Stated over any Euclidean domain with a gcd, and phrased with Mathlib's IsCoprime, which over the integers means the gcd is one.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
0fac0618978c · pair key 3abf10133367.
Nat.coprime_div_gcd_div_gcd special case
theorem Nat.coprime_div_gcd_div_gcd {m n : Nat} : 0 < m.gcd n → (m / m.gcd n).Coprime (n / m.gcd n)
Init.Data.Nat.Coprime · lines 63–65
Why a special case: Its binders are ℕ, so it reaches the nonnegative instances of the passage; Nat.Coprime is by definition the gcd being one.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
29f4ff4ffd1c · pair key 6130d36e3acf.
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Lean core states this exactly (proved).
The GCD is a commutative function: gcd(a, b) = gcd(b, a).
Show in article · Read it in context on Wikipedia ↗
Int.gcd_comm exact match
theorem Int.gcd_comm (a b : Int) : a.gcd b = b.gcd a
Init.Data.Int.Gcd · line 103
Note: Lean's gcd of two integers is the natural number the article calls the greatest common divisor, and at the pair of zeros it returns zero, the value the article also adopts there.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
9e6942af1ee2 · pair key 58d52d035b58.
gcd_comm more general
theorem gcd_comm {α : Type*} [CommMonoidWithZero α] [NormalizedGCDMonoid α] (a b : α) : GCDMonoid.gcd a b = GCDMonoid.gcd b a
Mathlib.Algebra.GCDMonoid.Basic · lines 389–392
Why more general: Stated for every carrier with a normalized gcd operation, the integers being one such carrier.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
843362ce4a3f · pair key 219ab06424b8.
Nat.gcd_comm special case
theorem Nat.gcd_comm (m n : Nat) : m.gcd n = n.gcd m
Init.Data.Nat.Gcd · lines 109–112
Why a special case: Its two binders are natural numbers, so it covers the swap identity only for nonnegative arguments.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
9ac30fde77d0 · pair key 7db6fd79fe80.
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Lean core states this up to a convention difference (proved).
The GCD is an associative function: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).
Show in article · Read it in context on Wikipedia ↗
Int.gcd_assoc close match
theorem Int.gcd_assoc (a b c : Int) : (↑(a.gcd b)).gcd c = a.gcd ↑(b.gcd c)
Init.Data.Int.Gcd · line 118
Why close, not exact: Lean's gcd of two integers is a natural number, so the declaration casts the inner gcd back into the integers before taking the outer one, and both sides name the two nested gcds of the passage's identity.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
1107dcfb757e · pair key 638d41fb06fd.
gcd_assoc more general
theorem gcd_assoc {α : Type*} [CommMonoidWithZero α] [NormalizedGCDMonoid α] (m n k : α) : GCDMonoid.gcd (GCDMonoid.gcd m n) k = GCDMonoid.gcd m (GCDMonoid.gcd n k)
Mathlib.Algebra.GCDMonoid.Basic · lines 398–404
Why more general: Stated for every carrier with a normalized gcd operation, with the integers as one instance of that structure.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
a611d55e0695 · pair key 0ea7a1c505e4.
Nat.gcd_assoc special case
theorem Nat.gcd_assoc (m n k : Nat) : (m.gcd n).gcd k = m.gcd (n.gcd k)
Init.Data.Nat.Gcd · lines 122–131
Why a special case: Its three binders are natural numbers, so it covers the identity only for nonnegative arguments.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
dbf12f6e19b8 · pair key 9b3bfc7dd187.
Sign in to tag this passage
-
Notation · supporting · Properties
✓Formalized
Formalized: Mathlib states a more general result (a definition).
Thus gcd(a, b, c, ...) can be used to denote the GCD of multiple arguments.
Show in article · Read it in context on Wikipedia ↗
Finset.gcd more general
def Finset.gcd {α : Type*} {β : Type*} [CommMonoidWithZero α] [NormalizedGCDMonoid α] : Finset β → (β → α) → α
Mathlib.Algebra.GCDMonoid.Finset · lines 124–125
Why more general: The declaration defines the gcd of a finite indexed family over any carrier with a normalized gcd, where the passage writes the gcd of several integers; a Mathlib statement such as isCoprime_of_gcd_eq_one_of_FLT uses it in exactly that way for three integers.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
5100ac4e09b4 · pair key f3ad1358d927.
Multiset.gcd more general
def Multiset.gcd {α : Type*} [CommMonoidWithZero α] [NormalizedGCDMonoid α] : Multiset α → α
Mathlib.Algebra.GCDMonoid.Multiset · lines 119–120
Why more general: It defines the gcd of a finite collection of elements of any carrier with a normalized gcd, which at the integers is the many-argument gcd the passage's notation denotes.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
0adbf2a3fc4f · pair key 2547711a6a21.
Sign in to tag this passage
-
Theorem · main statement · Properties
◔Partial
Partial: Lean core states a special case (proved).
The GCD is a multiplicative function in the following sense: if a1 and a2 are relatively prime, then gcd(a1⋅a2, b) = gcd(a1, b)⋅gcd(a2, b).
Show in article · Read it in context on Wikipedia ↗
Nat.Coprime.mul_gcd special case
theorem Nat.Coprime.mul_gcd {m n : Nat} : m.Coprime n → ∀ (k : Nat), (m * n).gcd k = m.gcd k * n.gcd k
Init.Data.Nat.Coprime · lines 184–185
Why a special case: Its binders are natural numbers and its coprimality hypothesis is Nat.Coprime, so it states the passage's identity for nonnegative a1, a2 and b.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
88859ed38559 · pair key 3834f1c31006.
Related, but states something else
Nat.Coprime.gcd_mul related
theorem Nat.Coprime.gcd_mul {m n : Nat} (k : Nat) : m.Coprime n → k.gcd (m * n) = k.gcd m * k.gcd n
Init.Data.Nat.Coprime · lines 177–182
How it differs: Again stated for natural numbers, so it reaches the passage's identity only for nonnegative arguments.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack, which downgraded it. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
e0af43645a2a · pair key af87fba27dd8.
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Lean core states this up to a convention difference (proved).
gcd(a, b) is closely related to the least common multiple lcm(a, b): we have gcd(a, b)⋅lcm(a, b) = |a⋅b|.
Show in article · Read it in context on Wikipedia ↗
Int.gcd_mul_lcm close match
theorem Int.gcd_mul_lcm (m n : Int) : m.gcd n * m.lcm n = m.natAbs * n.natAbs
Init.Data.Int.Gcd · lines 450–451
Why close, not exact: Lean's gcd and lcm of two integers are natural numbers, and the declaration writes its right-hand side in that natural-number encoding as the product of the two absolute values, the number the passage writes as the absolute value of the product.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
82936dbfa668 · pair key 70620c03fc94.
Nat.gcd_mul_lcm special case
theorem Nat.gcd_mul_lcm (m n : Nat) : m.gcd n * m.lcm n = m * n
Init.Data.Nat.Lcm · lines 38–40
Why a special case: Its binders are natural numbers, so it reaches the passage's identity only for nonnegative a and b.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
ace173d3f63c · pair key 62b61cd450bf.
PNat.gcd_mul_lcm special case
theorem PNat.gcd_mul_lcm (n m : ℕ+) : n.gcd m * n.lcm m = n * m
Mathlib.Data.PNat.Prime · lines 86–87
Why a special case: It is stated for the positive integers presented as the type of positive naturals.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
a05232222581 · pair key d208a84e52a8.
Sign in to tag this passage
-
Theorem · main statement · Properties
✕Not formalized
The following versions of distributivity hold true: gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c)) lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c)).
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt 3d159eefccb3). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · main statement · Properties
✕Not formalized
The following versions of distributivity hold true: gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c)) lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c)).
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt eb665a329925). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Mathlib states this up to a convention difference (proved).
If we have the unique prime factorizations of a = p1e1 p2e2 ⋅⋅⋅ pmem and b = p1f1 p2f2 ⋅⋅⋅ pmfm where ei ≥ 0 and fi ≥ 0, then the GCD of a and b is gcd(a,b) = p1min(e1,f1) p2min(e2,f2) ⋅⋅⋅ pmmin(em,fm).
Show in article · Read it in context on Wikipedia ↗
Nat.factorization_gcd close match
theorem Nat.factorization_gcd {a b : ℕ} : a ≠ 0 → b ≠ 0 → (a.gcd b).factorization = a.factorization ⊓ b.factorization
Mathlib.Data.Nat.Factorization.Basic · lines 355–368
Why close, not exact: The declaration carries each number's prime factorization as the finitely supported exponent function Nat.factorization, whose binders are natural numbers as the passage's factorized a and b are, and it says that each prime's exponent in the gcd is the smaller of its exponents in a and in b.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
ed8b66504a34 · pair key b683b3f03630.
PNat.factorMultiset_gcd close match
theorem PNat.factorMultiset_gcd (m n : ℕ+) : (m.gcd n).factorMultiset = m.factorMultiset ⊓ n.factorMultiset
Mathlib.Data.PNat.Factors · lines 354–363
Why close, not exact: It writes each positive integer's factorization as a multiset of primes and states that the gcd's multiset is the meet of the two, keeping each prime with the smaller of its two multiplicities.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
3dad45e59e6f · pair key e9981e2b6b9e.
TauCeti.Nat.prodPrimePow_gcd special case
theorem TauCeti.Nat.prodPrimePow_gcd {N : ℕ} {s t : Finset ℕ} : s ⊆ N.primeFactors → t ⊆ N.primeFactors → TauCeti.Nat.prodPrimePow N (s ∩ t) = (TauCeti.Nat.prodPrimePow N s).gcd (TauCeti.Nat.prodPrimePow N t)
TauCeti.Data.Nat.ExactDivisor · lines 427–450
Why a special case: Its two numbers share each exponent they both carry, so the minimum in the passage's formula reduces to that common exponent or to zero.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
83245ab. - Location key
874c1226d1e9 · pair key a7492fd079a2.
Sign in to tag this passage
-
Definition · supporting · Properties
✓Formalized
Formalized by 2 parts together (more general):
Nat.gcd_zero_left Lean core (proved)- the greatest common divisor of 0 and 0 is taken to be 0
Nat.lcm_zero_left Lean core (proved)- the least common multiple of 0 and 0 is taken to be 0
It is sometimes useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with GCD as meet and LCM as join operation.
Show in article · Read it in context on Wikipedia ↗
Nat.gcd_zero_left states part
theorem Nat.gcd_zero_left (y : Nat) : Nat.gcd 0 y = y
Init.Data.Nat.Gcd · lines 43–44
Why only part: Lean core fixes the left argument at zero and quantifies over the right one, and the value it gives at a right argument of zero is zero, the number the passage sets.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
976b7d4fabe3 · pair key 7aabcc205ec1.
Nat.lcm_zero_left states part
theorem Nat.lcm_zero_left (m : Nat) : Nat.lcm 0 m = 0
Init.Data.Nat.Lcm · line 59
Why only part: Lean core fixes the left argument at zero and quantifies over the right one, returning zero throughout, so the passage's case is covered.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
c9afcdd. - Location key
5882a0b2d10e · pair key 73155c49d285.
Sign in to tag this passage
-
Theorem · main statement · Properties
◔Partial
Partial: Mathlib states part of this (a definition).
It is sometimes useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with GCD as meet and LCM as join operation.[22]
Show in article · Read it in context on Wikipedia ↗
instStrongNormalizedGCDMonoidNat states part
instance instStrongNormalizedGCDMonoidNat : StrongNormalizedGCDMonoid ℕ
Mathlib.Algebra.GCDMonoid.Nat · lines 49–53
Why only part: The instance supplies the divisibility meet and join on the naturals, with the zero conventions the passage adopts, but it says nothing about infima of infinite families or about the distributive law.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
bb73067925a5 · pair key f60fb7c643ef.
Sign in to tag this passage
-
Theorem · main statement · Properties
✕Not formalized
In a Cartesian coordinate system, gcd(a, b) can be interpreted as the number of segments between points with integral coordinates on the straight line segment joining the points (0, 0) and (a, b).
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 9fc783fdaf48). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Mathlib states a more general result (proved).
For non-negative integers a and b, where a and b are not both zero, provable by considering the Euclidean algorithm in base n:[23] gcd(na − 1, nb − 1) = ngcd(a,b) − 1.
Show in article · Read it in context on Wikipedia ↗
Nat.pow_sub_one_gcd_pow_sub_one more general
theorem Nat.pow_sub_one_gcd_pow_sub_one (a b c : ℕ) : (a ^ b - 1).gcd (a ^ c - 1) = a ^ b.gcd c - 1
Mathlib.Data.Nat.GCD.Basic · lines 68–73
Why more general: Mathlib states this for naturals, and the passage's non-negative integers are exactly ℕ; subtraction is truncated there, which bites only in the degenerate cases where both sides come out zero, and the lemma drops the passage's condition that the exponents are not both zero.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
0b441f9233f2 · pair key 601571b01e30.
Sign in to tag this passage
-
Theorem · main statement · Properties
✓Formalized
Formalized: Mathlib states this up to a convention difference (proved).
An identity involving Euler's totient function: gcd(a, b) = ∑k|a and k|b φ(k).
Show in article · Read it in context on Wikipedia ↗
Nat.sum_totient close match
theorem Nat.sum_totient (n : ℕ) : n.divisors.sum Nat.totient = n
Mathlib.Data.Nat.Totient · lines 163–172
Why close, not exact: Mathlib indexes the sum by the ℕ-divisors of a single number, and at the gcd those are precisely the positive numbers dividing both a and b that the passage sums over, so writing the index set either way picks out the same finite set of positive divisors.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
5b0acd43c2de · pair key c2481acdb293.
Nat.sum_totient' close match
theorem Nat.sum_totient' (n : ℕ) : ∑ m ∈ Finset.range n.succ with m ∣ n, m.totient = n
Mathlib.Data.Nat.Totient · lines 174–177
Why close, not exact: This variant writes the index set as the naturals below the number that divide it, which at the gcd lists the positive common divisors of a and b, the ones the passage sums over.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
ae5c2eaf2d83 · pair key 7b71c525deae.
Sign in to tag this passage
-
Theorem · main statement · Properties
◔Partial
Partial: ATLAS (atlas-lean) states part of this (proved).
∑nk = 1 gcd(k, n) = ∑d|n dφ(nd) = n∑d|n φ(d)d = n∏p|n(1 + νp(n)(1 − 1p)) where νp(n) is the p-adic valuation.
Show in article · Read it in context on Wikipedia ↗
MetaMathlibExt.gcd_sum_eq_totient_sum states part
theorem MetaMathlibExt.gcd_sum_eq_totient_sum (n : ℕ) : 0 < n → ∑ j ∈ Finset.Icc 1 n, ↑(j.gcd n) = ↑n * ∑ d ∈ n.divisors, ↑d.totient / ↑d
MathlibExt.NumberTheory.ArithmeticFunction.GcdSumTotient · line 72
Why only part: The atlas theorem reaches one of the expressions the passage lists for the gcd summatory function, but not the product over the primes dividing n that the passage ends with.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
64c2773. - Location key
35d14a0405dc · pair key 1d79fe45b314.
Sign in to tag this passage
-
Theorem · main statement · Probabilities and expected value
✕Not formalized
In 1972, James E. Nymann showed that k integers, chosen independently and uniformly from {1, ..., n}, are coprime with probability 1/ζ(k) as n goes to infinity, where ζ refers to the Riemann zeta function.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 225568860532). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · main statement · Probabilities and expected value
✕Not formalized
(See coprime for a derivation.) This result was extended in 1987 to show that the probability that k random integers have greatest common divisor d is d−k/ζ(k).
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 505b33618f24). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · Probabilities and expected value
✕Not formalized
Using this information, the expected value of the greatest common divisor function can be seen (informally) to not exist when k = 2.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt fc70e8ee14f2). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · supporting · Probabilities and expected value
✕Not formalized
In this case the probability that the GCD equals d is d−2/ζ(2), so we have
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 1 candidates examined (receipt 66fa59640ec2). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · supporting · Probabilities and expected value
✕Not formalized
In this case the probability that the GCD equals d is d−2/ζ(2), so we have E(2) = ∑∞d = 1 d(d−2/ζ(2)) = 1ζ(2)∑∞d = 1 1d.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt a6055dc9d9c0). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · supporting · Probabilities and expected value
✓Formalized
Formalized: Mathlib states this up to a convention difference (proved).
This last summation is the harmonic series, which diverges.
Show in article · Read it in context on Wikipedia ↗
Real.tendsto_sum_range_one_div_nat_succ_atTop close match
theorem Real.tendsto_sum_range_one_div_nat_succ_atTop : Filter.Tendsto (fun n ↦ ∑ i ∈ Finset.range n, 1 / (↑i + 1)) Filter.atTop Filter.atTop
Mathlib.Analysis.PSeries · lines 361–365
Why close, not exact: Lean writes the terms as 1/(i+1) with i a natural number (ℕ) below n, which lists precisely the reciprocals of the positive integers the passage sums from d equal to one, so the same series is stated.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
ba126e02482c · pair key 3114b8179072.
Real.not_summable_one_div_natCast close match
theorem Real.not_summable_one_div_natCast : ¬Summable fun n ↦ 1 / ↑n
Mathlib.Analysis.PSeries · lines 357–358
Why close, not exact: Mathlib records divergence as the absence of a sum rather than as growth of the running totals, and indexes by natural numbers (ℕ) so that the one index outside the passage's positive d contributes zero.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
f0a1ff7be7c3 · pair key 1c761f44c1a0.
Sign in to tag this passage
-
Theorem · main statement · Probabilities and expected value
✕Not formalized
However, when k ≥ 3, the expected value is well-defined, and by the above argument, it is E(k) = ∑∞d = 1 d1 − kζ(k)−1 = ζ(k − 1)ζ(k).
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 3bf636fd9538). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · Probabilities and expected value
✕Not formalized
For k = 3, this is approximately equal to 1.3684.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 1 candidates examined (receipt c78dddd7eefd). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · supporting · Probabilities and expected value
✕Not formalized
For k = 4, it is approximately 1.1106.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 1 candidates examined (receipt e0de0773d105). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · main statement · In commutative rings
◔Partial
Partial: Mathlib states part of this (a definition).
The notion of greatest common divisor can more generally be defined for elements of an arbitrary commutative ring, although in general there need not exist one for every pair of elements.
Show in article · Read it in context on Wikipedia ↗
GCDMonoid states part
class GCDMonoid (α : Type*) [CommMonoidWithZero α]
Mathlib.Algebra.GCDMonoid.Basic · lines 307–323
Why only part: This is the generalized notion the passage describes, but Mathlib packages it as an assumption that gcds are available, so it does not record that some pair of ring elements can lack one.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
2c9ca461c2b7 · pair key 2fc944a0e6e5.
isGCDMonoid_iff_exists_gcd states part
theorem isGCDMonoid_iff_exists_gcd {α : Type*} [CommMonoidWithZero α] : IsGCDMonoid α ↔ IsCancelMulZero α ∧ ∀ (a b : α), ∃ c, ∀ (d : α), d ∣ a ∧ d ∣ b ↔ d ∣ c
Mathlib.Algebra.GCDMonoid.Basic · lines 1339–1342
Why only part: It states the divisibility definition of a gcd in the general setting and treats availability of gcds as a hypothesis, yet it does not exhibit a ring where a pair has none.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
14ecf7234d10 · pair key 5c1591da48c9.
Sign in to tag this passage
-
Definition · main statement · In commutative rings
◔Partial
Partial: Mathlib states a more general result, but as a proved theorem, not a definition; a definition passage is formalized only by a Lean definition.
If R is a commutative ring, and a and b are in R, then an element d of R is called a common divisor of a and b if it divides both a and b (that is, if there are elements x and y in R such that d·x = a and d·y = b).
Show in article · Read it in context on Wikipedia ↗
dvd_def more general
theorem dvd_def {α : Type*} [Semigroup α] {a b : α} : a ∣ b ↔ ∃ c, b = a * c
Mathlib.Algebra.Divisibility.Basic · lines 60–61
Why more general: Lean fixes divisibility for any semigroup, and a commutative ring supplies that structure.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
be4240f79075 · pair key b8cf3aa3541b.
dvd_iff_exists_eq_mul_right more general
theorem dvd_iff_exists_eq_mul_right {α : Type*} [Semigroup α] {a b : α} : a ∣ b ↔ ∃ c, b = a * c
Mathlib.Algebra.Divisibility.Basic · line 63
Why more general: This is the same equivalence under its longer name in Lean.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
a26ed8e51850 · pair key 48f59f83b6f2.
Related, but states something else
semigroupDvd related
instance semigroupDvd {α : Type*} [Semigroup α] : Dvd α
Mathlib.Algebra.Divisibility.Basic · lines 47–48
How it differs: This is the instance that attaches the divisibility notation to a ring.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
8677ed72f411 · pair key 855351dd76c2.
Sign in to tag this passage
-
Definition · main statement · In commutative rings
◔Partial
Partial: Mathlib states a special case (proved).
If d is a common divisor of a and b, and every common divisor of a and b divides d, then d is called a greatest common divisor of a and b.
Show in article · Read it in context on Wikipedia ↗
dvd_gcd_iff special case
theorem dvd_gcd_iff {α : Type*} [CommMonoidWithZero α] [GCDMonoid α] (a b c : α) : a ∣ GCDMonoid.gcd b c ↔ a ∣ b ∧ a ∣ c
Mathlib.Algebra.GCDMonoid.Basic · lines 385–387
Why a special case: Lean assumes that every pair of elements already has a chosen greatest common divisor, where the article only names the condition.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
f6064584bf38 · pair key 2d139f1dfd1a.
Related, but states something else
gcd_greatest_associated related
theorem gcd_greatest_associated {α : Type*} [CommMonoidWithZero α] [GCDMonoid α] {a b d : α} : d ∣ a → d ∣ b → (∀ (e : α), e ∣ a → e ∣ b → e ∣ d) → Associated d (GCDMonoid.gcd a b)
Mathlib.Algebra.GCDMonoid.Basic · lines 693–697
How it differs: Its hypotheses are written exactly as the article's condition.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
f1b85a11e1cd · pair key 3d7269860c7c.
isGCDMonoid_iff_exists_gcd related
theorem isGCDMonoid_iff_exists_gcd {α : Type*} [CommMonoidWithZero α] : IsGCDMonoid α ↔ IsCancelMulZero α ∧ ∀ (a b : α), ∃ c, ∀ (d : α), d ∣ a ∧ d ∣ b ↔ d ∣ c
Mathlib.Algebra.GCDMonoid.Basic · lines 1339–1342
How it differs: The article's condition appears inside this equivalence as the body of an existential.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
cb2e73687d2b · pair key 6188b840e0dd.
Sign in to tag this passage
-
Theorem · supporting · In commutative rings
✕Not formalized
With this definition, two elements a and b may very well have several greatest common divisors, or none at all.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt d07ea5aa4f3d). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · main statement · In commutative rings
✓Formalized
Formalized: Mathlib states a more general result (proved).
If R is an integral domain, then any two GCDs of a and b must be associate elements, since by definition either one must divide the other.
Show in article · Read it in context on Wikipedia ↗
associated_of_dvd_dvd more general
theorem associated_of_dvd_dvd {M : Type*} [MonoidWithZero M] [IsLeftCancelMulZero M] {a b : M} : a ∣ b → b ∣ a → Associated a b
Mathlib.Algebra.GroupWithZero.Associated · lines 190–204
Why more general: Lean works in a monoid with zero whose left multiplications cancel, a setting the article's domain falls under.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
9f3a7661af44 · pair key 1eb2d477ff4c.
dvd_dvd_iff_associated more general
theorem dvd_dvd_iff_associated {M : Type*} [MonoidWithZero M] [IsLeftCancelMulZero M] {a b : M} : a ∣ b ∧ b ∣ a ↔ Associated a b
Mathlib.Algebra.GroupWithZero.Associated · lines 206–208
Why more general: Lean packages the implication and its converse into a single equivalence.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
69c641a19ebd · pair key 9bd6c426c4e0.
gcd_greatest_associated special case
theorem gcd_greatest_associated {α : Type*} [CommMonoidWithZero α] [GCDMonoid α] {a b d : α} : d ∣ a → d ∣ b → (∀ (e : α), e ∣ a → e ∣ b → e ∣ d) → Associated d (GCDMonoid.gcd a b)
Mathlib.Algebra.GCDMonoid.Basic · lines 693–697
Why a special case: It assumes that a gcd has been chosen for every pair, which the article does not require of its domain.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
3a6a4f31f0b1 · pair key e1cad01f5156.
Sign in to tag this passage
-
Theorem · supporting · In commutative rings
✕Not formalized
Indeed, if a GCD exists, any one of its associates is a GCD as well.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 4 candidates examined (receipt 844b32191d3b). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · main statement · In commutative rings
✕Not formalized
Existence of a GCD is not assured in arbitrary integral domains.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt 57309c2574de). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · main statement · In commutative rings
✓Formalized
Formalized: Mathlib states a more general result (proved).
However, if R is a unique factorization domain or any other GCD domain, then any two elements have a GCD.
Show in article · Read it in context on Wikipedia ↗
instIsGCDMonoidOfUniqueFactorizationMonoid more general
instance instIsGCDMonoidOfUniqueFactorizationMonoid (α : Type*) [CommMonoidWithZero α] [UniqueFactorizationMonoid α] : IsGCDMonoid α
Mathlib.RingTheory.UniqueFactorizationDomain.GCDMonoid · lines 50–51
Why more general: Lean records the property that every pair has a greatest common divisor as the class IsGCDMonoid, which is the article's gcd domain, so the second hypothesis named is the conclusion itself.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
606d9672fd5d · pair key 3238f7e4a3f6.
UniqueFactorizationMonoid.toGCDMonoid more general
def UniqueFactorizationMonoid.toGCDMonoid (α : Type*) [CommMonoidWithZero α] [UniqueFactorizationMonoid α] : GCDMonoid α
Mathlib.RingTheory.UniqueFactorizationDomain.GCDMonoid · lines 30–48
Why more general: Lean builds a chosen gcd operation together with a least common multiple, where the article asserts only that a greatest common divisor is available.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
60bba0a31379 · pair key 147b85291c12.
Related, but states something else
isGCDMonoid_iff_exists_gcd related
theorem isGCDMonoid_iff_exists_gcd {α : Type*} [CommMonoidWithZero α] : IsGCDMonoid α ↔ IsCancelMulZero α ∧ ∀ (a b : α), ∃ c, ∀ (d : α), d ∣ a ∧ d ∣ b ↔ d ∣ c
Mathlib.Algebra.GCDMonoid.Basic · lines 1339–1342
How it differs: It spells out the class as pointwise existence of a greatest common divisor.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
b1ee54d22b7d · pair key 3cead675e2b1.
Sign in to tag this passage
-
Construction · main statement · In commutative rings
✓Formalized
Formalized: Mathlib states this exactly (a definition).
If R is a Euclidean domain in which euclidean division is given algorithmically (as is the case for instance when R = F[X] where F is a field, or when R is the ring of Gaussian integers), then greatest common divisors can be computed using a form of the Euclidean algorithm based on the division procedure.
Show in article · Read it in context on Wikipedia ↗
EuclideanDomain.gcd exact match
def EuclideanDomain.gcd {R : Type u} [EuclideanDomain R] [DecidableEq R] : R → R → R
Mathlib.Algebra.EuclideanDomain.Defs · lines 180–185
Note: Lean's function recurses on the remainder of the division and uses a decidable equality test to stop, which is the effective division the article assumes.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
6aef48ef3d37 · pair key 73ca9cd8ef4d.
EuclideanDomain.gcd_val close match
theorem EuclideanDomain.gcd_val {R : Type u} [EuclideanDomain R] [DecidableEq R] (a b : R) : EuclideanDomain.gcd a b = EuclideanDomain.gcd (b % a) a
Mathlib.Algebra.EuclideanDomain.Basic · lines 133–135
Why close, not exact: Lean writes the recursion step as an equation on the gcd function, exchanging the arguments for the remainder and the divisor.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
aa8b9be44486 · pair key 232440f61d61.
EuclideanDomain.gcdMonoid more general
def EuclideanDomain.gcdMonoid (R : Type*) [EuclideanDomain R] [DecidableEq R] : GCDMonoid R
Mathlib.RingTheory.EuclideanDomain · lines 70–78
Why more general: Lean packages the computed gcd together with a least common multiple into a single structure.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 3 for this passage, medium confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
6426a55e9dfa · pair key 2c8c07f84d55.
Sign in to tag this passage
-
Example · main statement · In commutative rings
✕Not formalized
The following is an example of an integral domain with two elements that do not have a GCD: R = ℤ[√−3 ], a = 4 = 2 ⋅ 2 = (1 + √−3 )(1 − √−3 ), b = (1 + √−3 ) ⋅ 2.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 5 queries and 3 candidates examined (receipt 918ed3c15b61). - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: upheld.
Sign in to tag this passage
-
Theorem · supporting · In commutative rings
✕Not formalized
The elements 2 and 1 + √−3 are two maximal common divisors (that is, any common divisor which is a multiple of 2 is associated to 2, the same holds for 1 + √−3, but they are not associated, so there is no greatest common divisor of a and b.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt 59687bdcd4e9). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Theorem · supporting · In commutative rings
✕Not formalized
The elements 2 and 1 + √−3 are two maximal common divisors (that is, any common divisor which is a multiple of 2 is associated to 2, the same holds for 1 + √−3, but they are not associated, so there is no greatest common divisor of a and b.
Show in article · Read it in context on Wikipedia ↗
✕Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).
Details
- Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 8bbf77582759). - Not re-checked: sampled out of challenge run
chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
Sign in to tag this passage
-
Construction · main statement · In commutative rings
◔Partial
Partial: Mathlib states a more general result, but as a proved theorem, not a definition; a construction passage is formalized only by a Lean definition.
Corresponding to the Bézout property we may, in any commutative ring, consider the collection of elements of the form pa + qb, where p and q range over the ring.
Show in article · Read it in context on Wikipedia ↗
Ideal.mem_span_pair more general
theorem Ideal.mem_span_pair {α : Type u} [Semiring α] {x y z : α} : z ∈ Ideal.span {x, y} ↔ ∃ a b, a * x + b * y = z
Mathlib.RingTheory.Ideal.Span · lines 153–154
Why more general: Lean records the collection as membership in the span of the two-element set, with the coefficients written on the left of each factor, and states it for every semiring, which is a wider class than the passage's commutative rings.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
b630316e901d · pair key ced48efbc3a6.
Sign in to tag this passage
-
Definition · main statement · In commutative rings
◔Partial
Partial: Mathlib states a more general result, but as a proved theorem, not a definition; a definition passage is formalized only by a Lean definition.
This is the ideal generated by a and b, and is denoted simply (a, b).
Show in article · Read it in context on Wikipedia ↗
Ideal.mem_span_pair more general
theorem Ideal.mem_span_pair {α : Type u} [Semiring α] {x y z : α} : z ∈ Ideal.span {x, y} ↔ ∃ a b, a * x + b * y = z
Mathlib.RingTheory.Ideal.Span · lines 153–154
Why more general: Lean's name for the ideal the passage writes as (a, b) is the span of the two-element set, and the lemma pins down its elements by the combination formula; it is phrased elementwise and for arbitrary semirings.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
c67190ccc6b5 · pair key cd35f28a580f.
Sign in to tag this passage
-
Theorem · main statement · In commutative rings
✓Formalized
Formalized by 2 parts together (more general):
Submodule.IsPrincipal.mem_iff_generator_dvd Mathlib (proved)- in a ring whose ideals are all principal, the ideal generated by a and b consists of the multiples of some ring element d
Submodule.IsPrincipal.dvd_generator_span_iff Mathlib (proved)- such an element d is a greatest common divisor of a and b
In a ring all of whose ideals are principal (a principal ideal domain or PID), this ideal will be identical with the set of multiples of some ring element d; then this d is a greatest common divisor of a and b.
Show in article · Read it in context on Wikipedia ↗
Submodule.IsPrincipal.mem_iff_generator_dvd states part
theorem Submodule.IsPrincipal.mem_iff_generator_dvd {R : Type u} [CommSemiring R] (S : Ideal R) [Submodule.IsPrincipal S] {x : R} : x ∈ S ↔ Submodule.IsPrincipal.generator S ∣ x
Mathlib.RingTheory.PrincipalIdealDomain · lines 135–136
Why only part: The lemma is stated for an arbitrary principal ideal of a commutative semiring, so it reaches well past the pair ideal of a principal ideal domain, and Lean expresses being a multiple of d as divisibility by d.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 1 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
2dbd9af11dd9 · pair key b22beb0bd40f.
Submodule.IsPrincipal.dvd_generator_span_iff states part
theorem Submodule.IsPrincipal.dvd_generator_span_iff {R : Type u} [CommSemiring R] {r : R} {s : Set R} [Submodule.IsPrincipal (Ideal.span s)] : r ∣ Submodule.IsPrincipal.generator (Ideal.span s) ↔ ∀ x ∈ s, r ∣ x
Mathlib.RingTheory.PrincipalIdealDomain · lines 157–162
Why only part: This is the divisibility-preorder reading of being a greatest common divisor that the article itself adopts, and the lemma gives it for any generating set whose span is principal.
Details
- Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run
loc-tierA-b1b by jack: candidate 2 for this passage, high confidence. - Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run
chal-tierA-b1 by jack: it survived. - Record set
tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a. - Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit
3dfb8e2. - Location key
cda011e8651e · pair key 1fead9e96f19.
Sign in to tag this passage