Coprime matchings of divisor sets
Abstract
For a positive integer n, let D(n) be its set of positive divisors and put N:=τ(n)=|D(n)|. We characterize the arithmetic progressions 𝒫 of length N that admit a bijection with D(n) pairing relatively prime integers. Such a coprime matching exists if and only if, for every prime p| n, at most N/(νp(n)+1) terms of 𝒫 are divisible by p, where νp(n) is the exponent of p in n. Call n an M-number if ppnmid n for every prime p. We prove that D(n) can be matched with every primitive arithmetic progression of length N, meaning one whose first term and common difference are coprime, if and only if n is an M-number. This proves a conjecture of McNew and Pomerance. We call n \emph{matchable} if D(n) admits a coprime matching with the primitive arithmetic progression {1,2,…,N}. The general criterion implies that n is matchable if and only if ⌊ N/p⌋≤ N/(νp(n)+1) for all p| n. We explicitly classify the matchable non-M-numbers, settle a conjectured divisor criterion, and prove that every divisor of a matchable integer is matchable. A Vandermonde determinant gives the required matchings under bounds on the prime exponents, while a partition into shorter progressions handles the remaining cases.
Related
- Hamilton cycles in bicirculants with non-coprime connection sets
- Matchings and shape-Wilf-Equivalence of sets of patterns of length three I: Triples
- Matchings and shape-Wilf-Equivalence of sets of patterns of length three II: Quadruples and Quintuples
- Exceptional sets for compositions involving Euler's function,the divisor-sum function and Dedekind's function
- The Brauer A(∞) condition and Navarro's conjecture on Brauer characters under coprime actions
BibTeX
@misc{alekseyev2026coprime,
title = {{Coprime matchings of divisor sets}},
author = {Max A. Alekseyev},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37512},
eprint = {2610.37512},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37512},
}
RIS
TY - UNPB
TI - Coprime matchings of divisor sets
AU - Max A. Alekseyev
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37512
UR - https://arxiv.org/abs/2610.37512
AB - For a positive integer n, let D(n) be its set of positive divisors and put N:=τ(n)=|D(n)|. We characterize the arithmetic progressions 𝒫 of length N that admit a bijection with D(n) pairing relatively prime integers. Such a coprime matching exists if and only if, for every prime p| n, at most N/(ν_p(n)+1) terms of 𝒫 are divisible by p, where ν_p(n) is the exponent of p in n. Call n an M-number if p^pnmid n for every prime p. We prove that D(n) can be matched with every primitive arithmetic progression of length N, meaning one whose first term and common difference are coprime, if and only if n is an M-number. This proves a conjecture of McNew and Pomerance. We call n \emph{matchable} if D(n) admits a coprime matching with the primitive arithmetic progression {1,2,…,N}. The general criterion implies that n is matchable if and only if ⌊ N/p⌋≤ N/(ν_p(n)+1) for all p| n. We explicitly classify the matchable non-M-numbers, settle a conjectured divisor criterion, and prove that every divisor of a matchable integer is matchable. A Vandermonde determinant gives the required matchings under bounds on the prime exponents, while a partition into shorter progressions handles the remaining cases.
ER -