Lemma 2.2 — coprimality of via the prime factors of
ProvedKnodelPrimeCordial.lemma_2_2gcdnumber-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be positive integers and let be the prime factorization of , with distinct primes. Then
When (so ) the right-hand side is empty and are coprime. The paper uses this criterion to label edges and whose end labels differ by or .
Formalization Note The primes are Nat.primeFactors |x − y|, with computed in ; "" is x % p ≠ 0.
Differences from the source:
- encoding: |x − y| = p1^α1 ⋯ pt^αt (a product of prime powers, hence ≥ 1) → hypothesis x ≠ y; reason: the printed factorization exists exactly when x ≠ y; without it x = y = 2 would be a counterexample
- encoding: the distinct primes p1, …, pt of the factorization → Nat.primeFactors (Int.natAbs (x − y)); reason: same finite set of primes
- encoding: x ≢ 0 mod p_i → x % p ≠ 0; reason: same condition
Preamble
import Mathlib
Formal statement
namespace KnodelPrimeCordial
/-- **Lemma 2.2** (Haque, Khanam, Shahriar, *Prime cordial labeling of Knödel graph*,
manuscript (2026), §2, p.3): "Let x, y be two positive integers, and let |x − y| =
p1^α1 p2^α2 . . . pt^αt, where pi are distinct prime factors and αi are their orders. Then they
are coprime iff x ≢ 0 mod pi for 1 ≤ i ≤ t."
For positive integers `x ≠ y`, `x` and `y` are coprime iff `x mod p ≠ 0` for every prime `p`
dividing `|x − y|`.
**Formalization Note** The primes `p₁, …, p_t` of the factorization of `|x − y|` are
`Nat.primeFactors |x − y|`, with `|x − y|` computed in `ℤ`. The hypothesis `x ≠ y` encodes the
printed factorization hypothesis: `|x − y|` is a (possibly empty) product of prime powers,
hence at least `1`. -/
theorem lemma_2_2 (x y : ℕ) (hx : 0 < x) (hy : 0 < y) (hxy : x ≠ y) :
Nat.Coprime x y ↔ ∀ p ∈ (Int.natAbs ((x : ℤ) - (y : ℤ))).primeFactors, x % p ≠ 0 := by sorry
end KnodelPrimeCordial
Source
Haque, Khanam, Shahriar, Prime cordial labeling of Knödel graph, manuscript (2026) (held version, sha256 366502170d8d7c65ccc2fcc6f5373dac872d6efdc838ba9e671eb578e4c08c60), Lemma 2.2, p.3 (PDF p.3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.