is_m_number_of_strongly_matchable
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$.
$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.
uses
Nat.mul_div_lehave 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
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.
uses
Nat.div_pos_iffby_cases h0 : N / (p + 1) = 0 · rw [h0] have : 0 < (N + p - 1) / p := by rw [Nat.div_pos_iff] omega omega
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.
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
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$.
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_leftintro 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
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`.
uses
Finset.mem_coe,Finset.mem_product,Finset.mem_filter,Prod.extlet 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
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)$.
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_righthave 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⟩
$(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`.
uses
Finset.card_le_card_of_injOn,Finset.card_product,Finset.card_rangehave hcard_le := Finset.card_le_card_of_injOn f hmaps hinj rw [Finset.card_product, Finset.card_range] at hcard_le exact hcard_le
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$.
uses
one_dvd,zero_lt_one,Nat.coprime_one_right,one_mulintro 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
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$.
uses
Finset.mem_coe,Finset.mem_filter,Subtype.mem,dvd_add,dvd_rfl,dvd_gcdlet 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
$\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$.
uses
Subtype.ext,Finset.card_le_card_of_injOn,fin_card_filter_dvdhave 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
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.
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_ceilhave 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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