Take an integer and line up all its positive divisors. On the opposite side, write the first several counting numbers—one for each divisor. Can you pair them off so that every pair shares no prime factor? It sounds like a small puzzle with a potentially messy answer: each prime in the original integer could block a different collection of pairings.
For 4, the divisors are 1, 2 and 4. Pair 4 with 3, 2 with 1, and 1 with 2. Every pair is coprime: its two numbers share no factor except 1. So far, easy. But as an integer acquires more prime factors and more divisors, the possible clashes multiply. A divisor ruled out by one prime might also be the only candidate that avoids another.
Max A. Alekseyev’s new work studies precisely this kind of assignment, including a broader version where the numbers on the second side come from an arithmetic progression rather than simply starting at 1. The first clue is a capacity limit. Suppose a prime p occurs e times in the prime factorization of the integer. Among all its divisors, only one choice for the exponent of p—choosing none—produces a divisor not divisible by p. That leaves exactly one out of every e + 1 divisors available to pair with numbers containing p.
So if the progression contains too many multiples of p, the pairing is impossible. Let N be the number of divisors, and therefore the length of the progression. The number of progression terms divisible by p cannot exceed N divided by e + 1. That check is plainly necessary. The shock is what happens next: for arithmetic progressions, checking this limit separately for every prime is also sufficient.
That is a much stronger claim than it may sound. In a general matching problem, passing each individual check does not guarantee that all the choices can be made at once. Think of several bouncers at a crowded door: each may see enough open spots for their own guests, yet the same spots might be needed by everyone. Matching theory captures these collisions with conditions on groups of guests, not just individuals. Here, however, the shape of an arithmetic progression imposes enough structure that the prime-by-prime capacity checks already guarantee a complete coprime pairing.
The proof finds a route through that thicket using a matrix. Put the progression terms in rows and the divisors in columns. The researcher builds the entries so that an entry is zero when its row number and column divisor share a prime factor, and nonzero when they are coprime. A nonzero determinant certifies that at least one term in its expansion selects a nonzero entry from every row and column. Those selected entries are exactly a full set of coprime pairs.
Making that determinant stay nonzero takes some mathematical engineering. The proof reshapes the matrix into a Vandermonde matrix, a familiar structure whose determinant is nonzero when the numbers it is built from are distinct. When prime exponents make that direct construction awkward, the progression is split into shorter progressions and the smaller matchings are assembled back into one. The result is not merely a clever example: it gives a complete criterion for when a divisor set can be matched to any given arithmetic progression of the same length.
Then comes a sharper question. What if the divisors must match every primitive arithmetic progression of the right length? A progression is primitive when its first term and step have no common factor. The answer turns on a striking threshold: every such progression can be matched exactly when no prime p has its pth power dividing the integer. In notation, the forbidden factor is pp.
Why should that particular power matter? If p occurs at least p times in the integer, then fewer than N divided by p of its divisors avoid p. But choose a primitive progression that starts on a multiple of p. It contains at least N divided by p multiples of p, rounded up. Each one needs a divisor that avoids p, and there are not enough. A single deliberately chosen progression exposes the shortage. On the other hand, when every prime exponent stays below that threshold, the paper’s determinant construction provides a matching for every primitive progression.
The number 4 makes the distinction tangible. It does have the forbidden factor 2 squared, so it cannot work against every primitive progression. Yet it matches perfectly with 1, 2, 3. Change the lineup to 2, 3, 4, and the two even numbers both need the only even-free divisor, 1. One particular lineup succeeds; the promise to succeed against every lineup fails. The paper also gives an exact criterion for this more forgiving, one-progression version, and proves a surprising inheritance rule: every divisor of a matchable integer is matchable too.
There is even a population-level payoff. The fraction of positive integers up to a growing bound that meet the universal, every-progression condition approaches 0.72199023441955… The simple prime-power rule makes that proportion possible to calculate. What began as a fussy pairing game has exposed a clean boundary between local shortages and global compatibility: in this special setting, each prime can be checked on its own, and the arithmetic progression quietly makes the checks fit together.
