AFTD Auto-Formalizing Theoretical Domains

is_m_number_of_strongly_matchable

theoremverified

If a positive integer n is strongly matchable, then n is an M-number.

Statement

theorem is_m_number_of_strongly_matchable (n : ℕ) (hn : 0 < n) (hm : is_strongly_matchable n) :
    is_m_number n
Source
arXiv:2610.37512 Section 3
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • is_m_numberA natural number n is an M-number if for every prime p, p^p does not divide n.
  • is_strongly_matchableA natural number n is strongly matchable if for every pair of natural numbers a and b with 0 < b and Nat.Coprime a b, there exists an…
  • fin_card_filter_dvdFor m > 0, exactly (k + m - 1)/m of the positions 0, ..., k-1 are multiples of m.

Read back from the Lean

For any natural number $n$, if $n > 0$ and $n$ is strongly matchable, then $n$ is an m-number.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that every strongly matchable positive integer $n$ is an M-number, we suppose for contradiction that $p^p \mid n$ for some prime $p$. By strong matchability with the progression $p + i$, the divisors of $n$ are in bijection with the indices $0 \le i < N$, where $N = |\mathrm{divisors}(n)|$. Every index divisible by $p$ must map to a divisor coprime to $p$, giving at least $\lceil N/p \rceil = \lfloor (N + p - 1) / p \rfloor$ such divisors. On the other hand, unique prime factorization shows that the number of divisors not divisible by $p$ is at most $\lfloor N/(p+1) \rfloor$. This forces $\lfloor (N + p - 1) / p \rfloor \le \lfloor N/(p+1) \rfloor$, which contradicts the elementary arithmetic fact that $\lfloor N/(p+1) \rfloor < \lfloor (N + p - 1) / p \rfloor$ for all $N > 0$ and $p \ge 2$.

  1. $p \lfloor N / (p + 1) \rfloor + \lfloor N / (p + 1) \rfloor \le N$.

    By integer division (`Nat.mul_div_le`), $(p + 1) \lfloor N / (p + 1) \rfloor \le N$. Expanding $(p + 1) x = p x + x$ via algebraic rearrangement gives the claim.

    lines 3–6

    uses Nat.mul_div_le

      have H : (p + 1) * (N / (p + 1)) ≤ N := Nat.mul_div_le N (p + 1)
      have H2 : p * (N / (p + 1)) + (N / (p + 1)) ≤ N := by
        calc p * (N / (p + 1)) + (N / (p + 1)) = (p + 1) * (N / (p + 1)) := by ring
        _ ≤ N := H
  2. The strict inequality $\lfloor N / (p + 1) \rfloor < \lfloor (N + p - 1) / p \rfloor$ holds when $\lfloor N / (p + 1) \rfloor = 0$.

    When $\lfloor N / (p + 1) \rfloor = 0$, the left-hand side is $0$. Since $N > 0$ and $p \ge 2$, the numerator $N + p - 1 \ge p > 0$, so $\lfloor (N + p - 1) / p \rfloor \ge 1 > 0$ by `Nat.div_pos_iff`. Linear arithmetic closes the goal.

    lines 7–12

    uses Nat.div_pos_iff

      by_cases h0 : N / (p + 1) = 0
      · rw [h0]
        have : 0 < (N + p - 1) / p := by
          rw [Nat.div_pos_iff]
          omega
        omega
  3. The strict inequality $\lfloor N / (p + 1) \rfloor < \lfloor (N + p - 1) / p \rfloor$ holds when $\lfloor N / (p + 1) \rfloor \ge 1$.

    Since $\lfloor N / (p + 1) \rfloor \ge 1$ (`Nat.pos_of_ne_zero`), we have $p \lfloor N / (p + 1) \rfloor \le N - 1$, so $(\lfloor N / (p + 1) \rfloor + 1) p \le N + p - 1$. Dividing both sides by $p$ via `Nat.le_div_iff_mul_le` yields $\lfloor N / (p + 1) \rfloor + 1 \le \lfloor (N + p - 1) / p \rfloor$, which implies the strict inequality.

    lines 13–21

    uses Nat.pos_of_ne_zero, Nat.le_div_iff_mul_le

      · have h1 : 1 ≤ N / (p + 1) := Nat.pos_of_ne_zero h0
        have h2 : (N / (p + 1) + 1) * p ≤ N + p - 1 := by
          calc (N / (p + 1) + 1) * p = p * (N / (p + 1)) + p := by ring
          _ ≤ (N - 1) + p := by omega
          _ = N + p - 1 := by omega
        have h3 : N / (p + 1) + 1 ≤ (N + p - 1) / p := by
          rw [Nat.le_div_iff_mul_le (by omega)]
          exact h2
        omega
  4. For $k_1 \le k_2$ and $d_1, d_2$ coprime to $p$, $p^{k_1} d_1 = p^{k_2} d_2$ implies $k_1 = k_2$ and $d_1 = d_2$.

    If $k_1 = k_2$, canceling $p^{k_1} > 0$ gives $d_1 = d_2$ via `Nat.eq_of_mul_eq_mul_left`. If $k_1 < k_2$, write $k_2 = k_1 + m + 1$ with $m \ge 0$ (`Nat.exists_eq_add_of_lt`). Canceling $p^{k_1}$ yields $d_1 = p^{m+1} d_2$, which means $p \mid d_1$, contradicting the assumption that $p \nmid d_1$.

    lines 26–44

    uses pow_pos, Nat.eq_of_mul_eq_mul_left, Nat.exists_eq_add_of_lt, pow_add, mul_assoc, dvd_pow_self, dvd_mul_of_dvd_left

      intro D0
      have hp_pos : 0 < p := hp.pos
      have hp_pow (k : ℕ) : 0 < p ^ k := pow_pos hp_pos k
      have H (k1 k2 d1 d2 : ℕ) (hpd1 : ¬ p ∣ d1) (hpd2 : ¬ p ∣ d2)
          (heq : p ^ k1 * d1 = p ^ k2 * d2) (hle : k1 ≤ k2) : k1 = k2 ∧ d1 = d2 := by
        rcases hle.eq_or_lt with rfl | hlt
        · have hd : d1 = d2 := Nat.eq_of_mul_eq_mul_left (hp_pow k1) heq
          exact ⟨rfl, hd⟩
        · obtain ⟨m, rfl⟩ : ∃ m, k2 = k1 + m + 1 := Nat.exists_eq_add_of_lt hlt
          have heq2 : d1 = p ^ (m + 1) * d2 := by
            apply Nat.eq_of_mul_eq_mul_left (hp_pow k1)
            calc p ^ k1 * d1 = p ^ (k1 + (m + 1)) * d2 := heq
            _ = (p ^ k1 * p ^ (m + 1)) * d2 := by rw [pow_add]
            _ = p ^ k1 * (p ^ (m + 1) * d2) := by rw [mul_assoc]
          have hdvd : p ∣ d1 := by
            rw [heq2]
            have : p ∣ p ^ (m + 1) := dvd_pow_self p (by omega)
            exact dvd_mul_of_dvd_left this d2
          exact (hpd1 hdvd).elim
  5. The map $f(k, d) = p^k d$ is injective on $S = \{0, \dots, p\} \times D_0$.

    Given two pairs in $S$ with the same image under $f$, by symmetry we may assume $k_1 \le k_2$. Applying the uniqueness helper established in the previous step gives $k_1 = k_2$ and $d_1 = d_2$, so the pairs are identical by `Prod.ext`.

    lines 45–58

    uses Finset.mem_coe, Finset.mem_product, Finset.mem_filter, Prod.ext

      let S := (Finset.range (p + 1)) ×ˢ D0
      let f : ℕ × ℕ → ℕ := fun x => p ^ x.1 * x.2
      have hinj : Set.InjOn f (S : Set (ℕ × ℕ)) := by
        intro ⟨k1, d1⟩ hx ⟨k2, d2⟩ hy heq
        rw [Finset.mem_coe, Finset.mem_product, Finset.mem_filter] at hx hy
        have hpd1 : ¬ p ∣ d1 := hx.2.2
        have hpd2 : ¬ p ∣ d2 := hy.2.2
        have h_pair : k1 = k2 ∧ d1 = d2 := by
          by_cases hle : k1 ≤ k2
          · exact H k1 k2 d1 d2 hpd1 hpd2 heq hle
          · have hle' : k2 ≤ k1 := by omega
            have := H k2 k1 d2 d1 hpd2 hpd1 heq.symm hle'
            exact ⟨this.1.symm, this.2.symm⟩
        exact Prod.ext h_pair.1 h_pair.2
  6. The map $f(k, d) = p^k d$ maps $S$ into the divisors of $n$.

    For $(k, d) \in S$, $k \le p$, $d \mid n$, and $p \nmid d$. Since $p$ is prime and does not divide $d$, $\gcd(p^p, d) = 1$ by `Nat.Coprime.pow_left`. Since $p^p \mid n$ and $d \mid n$, their product $p^p d$ divides $n$ (`Nat.Coprime.mul_dvd_of_dvd_of_dvd`). Because $k \le p$, $p^k \mid p^p$ (`Nat.pow_dvd_pow`), so $p^k d \mid p^p d \mid n$, proving $p^k d \in \mathrm{divisors}(n)$.

    lines 59–73

    uses Finset.mem_coe, Finset.mem_product, Finset.mem_range, Finset.mem_filter, Nat.mem_divisors, Nat.Coprime.pow_left, Nat.Coprime.mul_dvd_of_dvd_of_dvd, Nat.pow_dvd_pow, Nat.mul_dvd_mul_right

      have hmaps : Set.MapsTo f (S : Set (ℕ × ℕ)) (n.divisors : Set ℕ) := by
        intro ⟨k, d⟩ hx
        rw [Finset.mem_coe, Finset.mem_product, Finset.mem_range, Finset.mem_filter] at hx
        have hk : k ≤ p := by omega
        have hd_mem : d ∈ n.divisors := hx.2.1
        have hpd : ¬ p ∣ d := hx.2.2
        rw [Finset.mem_coe, Nat.mem_divisors]
        have hd_dvd : d ∣ n := (Nat.mem_divisors.mp hd_mem).1
        have hcp : Nat.Coprime (p ^ p) d := by
          apply Nat.Coprime.pow_left
          exact hp.coprime_iff_not_dvd.mpr hpd
        have hmul : p ^ p * d ∣ n := Nat.Coprime.mul_dvd_of_dvd_of_dvd hcp hpn hd_dvd
        have hpow : p ^ k ∣ p ^ p := Nat.pow_dvd_pow p hk
        have hdvd : p ^ k * d ∣ p ^ p * d := Nat.mul_dvd_mul_right hpow d
        exact ⟨hdvd.trans hmul, hn⟩
  7. $(p + 1) |D_0| \le |\mathrm{divisors}(n)|$.

    Because $f$ is injective from $S$ into $\mathrm{divisors}(n)$, $|S| \le |\mathrm{divisors}(n)|$ by `Finset.card_le_card_of_injOn`. Since $S = \{0, \dots, p\} \times D_0$, its cardinality is $(p + 1) |D_0|$ by `Finset.card_product` and `Finset.card_range`.

    lines 74–76

    uses Finset.card_le_card_of_injOn, Finset.card_product, Finset.card_range

      have hcard_le := Finset.card_le_card_of_injOn f hmaps hinj
      rw [Finset.card_product, Finset.card_range] at hcard_le
      exact hcard_le
  8. Assuming $p$ is prime and $p^p \mid n$, there exists a bijection $e : \{0, \dots, N-1\} \simeq \mathrm{divisors}(n)$ such that $\gcd(e(i), p + i) = 1$ for all $i$, where $N = |\mathrm{divisors}(n)| > 0$.

    We assume for contradiction that $p$ is prime and $p^p \mid n$. Since $1 \mid n$ and $n > 0$, $1 \in \mathrm{divisors}(n)$, so $N > 0$. By strong matchability of $n$ applied to the progression with $a = p$ and $b = 1$ (noting $b = 1 > 0$ and $\gcd(p, 1) = 1$), there exists a matching $e$ satisfying $\gcd(e(i), p + i) = 1$ for all $i < N$.

    lines 81–92

    uses one_dvd, zero_lt_one, Nat.coprime_one_right, one_mul

      intro p hp hpn
      let N := n.divisors.card
      have hN : 0 < N := by
        have : 1 ∈ n.divisors := Nat.mem_divisors.mpr ⟨one_dvd n, by omega⟩
        exact Finset.card_pos.mpr ⟨1, this⟩
      let D0 := n.divisors.filter (fun d => ¬ p ∣ d)
      obtain ⟨e, he⟩ := hm p 1 zero_lt_one (Nat.coprime_one_right p)
      have he_coprime : ∀ i : Fin N, Nat.Coprime (e i : ℕ) (p + (i : ℕ)) := by
        intro i
        have := he i
        rw [one_mul] at this
        exact this
  9. For every index $j < N$ divisible by $p$, the divisor $e(j)$ is not divisible by $p$, so $e(j) \in D_0$.

    If $p \mid j$, then $p \mid (p + j)$ by `dvd_add` and `dvd_rfl`. If $p$ also divided $e(j)$, then $p$ would divide $\gcd(e(j), p + j) = 1$ by `dvd_gcd`, contradicting the fact that a prime cannot divide $1$. Thus $p \nmid e(j)$, meaning $e(j) \in D_0$.

    lines 93–106

    uses Finset.mem_coe, Finset.mem_filter, Subtype.mem, dvd_add, dvd_rfl, dvd_gcd

      let s := Finset.univ.filter (fun j : Fin N => p ∣ (j : ℕ))
      let g : Fin N → ℕ := fun j => (e j : ℕ)
      have hmaps : Set.MapsTo g (s : Set (Fin N)) (D0 : Set ℕ) := by
        intro j hj
        rw [Finset.mem_coe, Finset.mem_filter] at hj ⊢
        have h_dvd : p ∣ (j : ℕ) := hj.2
        have h_mem : (e j : ℕ) ∈ n.divisors := Subtype.mem (e j)
        refine ⟨h_mem, ?_⟩
        intro hp_dvd
        have h_p_dvd_add : p ∣ p + (j : ℕ) := dvd_add dvd_rfl h_dvd
        have h_cp := he_coprime j
        have h_dvd_gcd : p ∣ Nat.gcd (e j : ℕ) (p + (j : ℕ)) := dvd_gcd hp_dvd h_p_dvd_add
        rw [h_cp] at h_dvd_gcd
        exact hp.not_dvd_one h_dvd_gcd
  10. $\lfloor (N + p - 1) / p \rfloor \le |D_0|$.

    Since $e$ is an equivalence, it restricts injectively to the set $s$ of indices divisible by $p$, which implies $|s| \le |D_0|$ via `Finset.card_le_card_of_injOn`. By `fin_card_filter_dvd`, the number of multiples of $p$ in $\{0, \dots, N-1\}$ is exactly $|s| = \lfloor (N + p - 1) / p \rfloor$.

    lines 107–114

    uses Subtype.ext, Finset.card_le_card_of_injOn, fin_card_filter_dvd

      have hinj : Set.InjOn g (s : Set (Fin N)) := by
        intro j1 _ j2 _ heq
        dsimp [g] at heq
        have : e j1 = e j2 := Subtype.ext heq
        exact e.injective this
      have hs_le_D0 : s.card ≤ D0.card := Finset.card_le_card_of_injOn g hmaps hinj
      have hs_card : s.card = (N + p - 1) / p := fin_card_filter_dvd p N hp.pos
      rw [hs_card] at hs_le_D0
  11. A contradiction arises between the lower bound on $|D_0|$ and Lemma 1, completing the proof.

    Lemma 2 (`is_m_number_of_strongly_matchable_aux_card_le`) gives $(p + 1) |D_0| \le N$, which rewrites via `Nat.le_div_iff_mul_le` and `mul_comm` to $|D_0| \le \lfloor N / (p + 1) \rfloor$. Chaining with the previous bound gives $\lfloor (N + p - 1) / p \rfloor \le \lfloor N / (p + 1) \rfloor$. But Lemma 1 (`is_m_number_of_strongly_matchable_aux_div_lt_div_ceil`) establishes the strict opposite inequality $\lfloor N / (p + 1) \rfloor < \lfloor (N + p - 1) / p \rfloor$. Linear arithmetic (`omega`) detects this contradiction and closes the goal.

    lines 115–123

    uses is_m_number_of_strongly_matchable_aux_card_le, Nat.le_div_iff_mul_le, mul_comm, is_m_number_of_strongly_matchable_aux_div_lt_div_ceil

      have hD0_mul : (p + 1) * D0.card ≤ N := is_m_number_of_strongly_matchable_aux_card_le n p (by omega) hp hpn
      have hD0_le : D0.card ≤ N / (p + 1) := by
        rw [Nat.le_div_iff_mul_le (by omega)]
        rw [mul_comm]
        exact hD0_mul
      have h_le : (N + p - 1) / p ≤ N / (p + 1) := hs_le_D0.trans hD0_le
      have h_lt : N / (p + 1) < (N + p - 1) / p :=
        is_m_number_of_strongly_matchable_aux_div_lt_div_ceil N p hN hp.two_le
      omega
Nat.mul_div_le
For any natural numbers $m$ and $n$, $n \cdot \lfloor m / n \rfloor \le m$.
Nat.div_pos_iff
The integer quotient $\lfloor a / b \rfloor$ is strictly positive if and only if $b > 0$ and $b \le a$.
Nat.pos_of_ne_zero
A non-zero natural number is strictly positive.
Nat.le_div_iff_mul_le
For $k > 0$, $x \le \lfloor y / k \rfloor$ if and only if $x \cdot k \le y$.
pow_pos
Any power of a strictly positive number is strictly positive.
Nat.eq_of_mul_eq_mul_left
A strictly positive factor can be cancelled from the left of an equality of natural numbers.
Nat.exists_eq_add_of_lt
If $m < n$, then $n = m + k + 1$ for some natural number $k$.
pow_add
Exponentiation distributes over addition: $a^{m+n} = a^m \cdot a^n$.
mul_assoc
Multiplication is associative.
dvd_pow_self
A number divides any of its positive powers.
dvd_mul_of_dvd_left
If $a$ divides $b$, then $a$ divides $b \cdot c$.
Finset.mem_coe
An element belongs to a finset coerced to a set if and only if it belongs to the finset.
Finset.mem_product
A pair belongs to a Cartesian product of two finsets if and only if its components belong to the respective sets.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the filter predicate.
Prod.ext
Two ordered pairs are equal if their corresponding first and second components are equal.
Finset.mem_range
A natural number belongs to $\mathrm{range}(n)$ if and only if it is strictly less than $n$.
Nat.mem_divisors
A number $n$ belongs to the divisors of $m$ if and only if $n \mid m$ and $m \ne 0$.
Nat.Coprime.pow_left
If $m$ and $k$ are coprime, then any power $m^n$ is also coprime to $k$.
Nat.Coprime.mul_dvd_of_dvd_of_dvd
If $m$ and $n$ are coprime and both divide $a$, then their product $m \cdot n$ divides $a$.
Nat.pow_dvd_pow
If $m \le n$, then $a^m$ divides $a^n$.
Nat.mul_dvd_mul_right
If $a$ divides $b$, then $a \cdot c$ divides $b \cdot c$.
Finset.card_le_card_of_injOn
If a function maps a finite set $s$ into a finite set $t$ injectively, then $|s| \le |t|$.
Finset.card_product
The cardinality of the Cartesian product of two finite sets is the product of their cardinalities.
Finset.card_range
The cardinality of $\mathrm{range}(n)$ is $n$.
one_dvd
The number $1$ divides any element.
zero_lt_one
The number $0$ is strictly less than $1$.
Nat.coprime_one_right
Any natural number is coprime to $1$.
one_mul
Multiplication by $1$ on the left is the identity.
Subtype.mem
An element of a subtype belongs to the underlying set.
dvd_add
If $a$ divides $b$ and $a$ divides $c$, then $a$ divides $b + c$.
dvd_rfl
Every number divides itself.
dvd_gcd
If $a$ divides $b$ and $a$ divides $c$, then $a$ divides $\gcd(b, c)$.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
fin_card_filter_dvd
The number of elements of $\mathrm{Fin}(k)$ divisible by $m$ is $\lfloor (k + m - 1) / m \rfloor$.
is_m_number_of_strongly_matchable_aux_card_le
If $n \ne 0$, $p$ is prime, and $p^p \mid n$, then $(p + 1) |D_0| \le |\mathrm{divisors}(n)|$, where $D_0$ is the set of divisors of $n$ not divisible by $p$.
mul_comm
Multiplication is commutative.
is_m_number_of_strongly_matchable_aux_div_lt_div_ceil
For any natural numbers $N > 0$ and $p \ge 2$, $\lfloor N / (p + 1) \rfloor < \lfloor (N + p - 1) / p \rfloor$.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

lemma is_m_number_of_strongly_matchable_aux_div_lt_div_ceil (N p : ℕ) (hN : 0 < N) (hp : 2 ≤ p) :    N / (p + 1) < (N + p - 1) / p := by  have H : (p + 1) * (N / (p + 1)) ≤ N := Nat.mul_div_le N (p + 1)  have H2 : p * (N / (p + 1)) + (N / (p + 1)) ≤ N := by    calc p * (N / (p + 1)) + (N / (p + 1)) = (p + 1) * (N / (p + 1)) := by ring    _ ≤ N := H  by_cases h0 : N / (p + 1) = 0  · rw [h0]    have : 0 < (N + p - 1) / p := by      rw [Nat.div_pos_iff]      omega    omega  · have h1 : 1 ≤ N / (p + 1) := Nat.pos_of_ne_zero h0    have h2 : (N / (p + 1) + 1) * p ≤ N + p - 1 := by      calc (N / (p + 1) + 1) * p = p * (N / (p + 1)) + p := by ring      _ ≤ (N - 1) + p := by omega      _ = N + p - 1 := by omega    have h3 : N / (p + 1) + 1 ≤ (N + p - 1) / p := by      rw [Nat.le_div_iff_mul_le (by omega)]      exact h2    omegalemma is_m_number_of_strongly_matchable_aux_card_le (n p : ℕ) (hn : n ≠ 0) (hp : p.Prime) (hpn : p ^ p ∣ n) :    let D0 := n.divisors.filter (fun d => ¬ p ∣ d)    (p + 1) * D0.card ≤ n.divisors.card := by  intro D0  have hp_pos : 0 < p := hp.pos  have hp_pow (k : ℕ) : 0 < p ^ k := pow_pos hp_pos k  have H (k1 k2 d1 d2 : ℕ) (hpd1 : ¬ p ∣ d1) (hpd2 : ¬ p ∣ d2)      (heq : p ^ k1 * d1 = p ^ k2 * d2) (hle : k1 ≤ k2) : k1 = k2 ∧ d1 = d2 := by    rcases hle.eq_or_lt with rfl | hlt    · have hd : d1 = d2 := Nat.eq_of_mul_eq_mul_left (hp_pow k1) heq      exact ⟨rfl, hd⟩    · obtain ⟨m, rfl⟩ : ∃ m, k2 = k1 + m + 1 := Nat.exists_eq_add_of_lt hlt      have heq2 : d1 = p ^ (m + 1) * d2 := by        apply Nat.eq_of_mul_eq_mul_left (hp_pow k1)        calc p ^ k1 * d1 = p ^ (k1 + (m + 1)) * d2 := heq        _ = (p ^ k1 * p ^ (m + 1)) * d2 := by rw [pow_add]        _ = p ^ k1 * (p ^ (m + 1) * d2) := by rw [mul_assoc]      have hdvd : p ∣ d1 := by        rw [heq2]        have : p ∣ p ^ (m + 1) := dvd_pow_self p (by omega)        exact dvd_mul_of_dvd_left this d2      exact (hpd1 hdvd).elim  let S := (Finset.range (p + 1)) ×ˢ D0  let f : ℕ × ℕ → ℕ := fun x => p ^ x.1 * x.2  have hinj : Set.InjOn f (S : Set (ℕ × ℕ)) := by    intro ⟨k1, d1⟩ hx ⟨k2, d2⟩ hy heq    rw [Finset.mem_coe, Finset.mem_product, Finset.mem_filter] at hx hy    have hpd1 : ¬ p ∣ d1 := hx.2.2    have hpd2 : ¬ p ∣ d2 := hy.2.2    have h_pair : k1 = k2 ∧ d1 = d2 := by      by_cases hle : k1 ≤ k2      · exact H k1 k2 d1 d2 hpd1 hpd2 heq hle      · have hle' : k2 ≤ k1 := by omega        have := H k2 k1 d2 d1 hpd2 hpd1 heq.symm hle'        exact ⟨this.1.symm, this.2.symm⟩    exact Prod.ext h_pair.1 h_pair.2  have hmaps : Set.MapsTo f (S : Set (ℕ × ℕ)) (n.divisors : Set ℕ) := by    intro ⟨k, d⟩ hx    rw [Finset.mem_coe, Finset.mem_product, Finset.mem_range, Finset.mem_filter] at hx    have hk : k ≤ p := by omega    have hd_mem : d ∈ n.divisors := hx.2.1    have hpd : ¬ p ∣ d := hx.2.2    rw [Finset.mem_coe, Nat.mem_divisors]    have hd_dvd : d ∣ n := (Nat.mem_divisors.mp hd_mem).1    have hcp : Nat.Coprime (p ^ p) d := by      apply Nat.Coprime.pow_left      exact hp.coprime_iff_not_dvd.mpr hpd    have hmul : p ^ p * d ∣ n := Nat.Coprime.mul_dvd_of_dvd_of_dvd hcp hpn hd_dvd    have hpow : p ^ k ∣ p ^ p := Nat.pow_dvd_pow p hk    have hdvd : p ^ k * d ∣ p ^ p * d := Nat.mul_dvd_mul_right hpow d    exact ⟨hdvd.trans hmul, hn⟩  have hcard_le := Finset.card_le_card_of_injOn f hmaps hinj  rw [Finset.card_product, Finset.card_range] at hcard_le  exact hcard_le/-- Every strongly matchable positive integer is an M-number. -/theorem is_m_number_of_strongly_matchable (n : ℕ) (hn : 0 < n) (hm : is_strongly_matchable n) :    is_m_number n := by  intro p hp hpn  let N := n.divisors.card  have hN : 0 < N := by    have : 1 ∈ n.divisors := Nat.mem_divisors.mpr ⟨one_dvd n, by omega⟩    exact Finset.card_pos.mpr ⟨1, this⟩  let D0 := n.divisors.filter (fun d => ¬ p ∣ d)  obtain ⟨e, he⟩ := hm p 1 zero_lt_one (Nat.coprime_one_right p)  have he_coprime : ∀ i : Fin N, Nat.Coprime (e i : ℕ) (p + (i : ℕ)) := by    intro i    have := he i    rw [one_mul] at this    exact this  let s := Finset.univ.filter (fun j : Fin N => p ∣ (j : ℕ))  let g : Fin N → ℕ := fun j => (e j : ℕ)  have hmaps : Set.MapsTo g (s : Set (Fin N)) (D0 : Set ℕ) := by    intro j hj    rw [Finset.mem_coe, Finset.mem_filter] at hj ⊢    have h_dvd : p ∣ (j : ℕ) := hj.2    have h_mem : (e j : ℕ) ∈ n.divisors := Subtype.mem (e j)    refine ⟨h_mem, ?_⟩    intro hp_dvd    have h_p_dvd_add : p ∣ p + (j : ℕ) := dvd_add dvd_rfl h_dvd    have h_cp := he_coprime j    have h_dvd_gcd : p ∣ Nat.gcd (e j : ℕ) (p + (j : ℕ)) := dvd_gcd hp_dvd h_p_dvd_add    rw [h_cp] at h_dvd_gcd    exact hp.not_dvd_one h_dvd_gcd  have hinj : Set.InjOn g (s : Set (Fin N)) := by    intro j1 _ j2 _ heq    dsimp [g] at heq    have : e j1 = e j2 := Subtype.ext heq    exact e.injective this  have hs_le_D0 : s.card ≤ D0.card := Finset.card_le_card_of_injOn g hmaps hinj  have hs_card : s.card = (N + p - 1) / p := fin_card_filter_dvd p N hp.pos  rw [hs_card] at hs_le_D0  have hD0_mul : (p + 1) * D0.card ≤ N := is_m_number_of_strongly_matchable_aux_card_le n p (by omega) hp hpn  have hD0_le : D0.card ≤ N / (p + 1) := by    rw [Nat.le_div_iff_mul_le (by omega)]    rw [mul_comm]    exact hD0_mul  have h_le : (N + p - 1) / p ≤ N / (p + 1) := hs_le_D0.trans hD0_le  have h_lt : N / (p + 1) < (N + p - 1) / p :=    is_m_number_of_strongly_matchable_aux_div_lt_div_ceil N p hN hp.two_le  omega
See it in the graphDiscuss this resultChallenge it