Kvant Math Problem 1014
Consider small examples of pairwise coprime numbers, such as $a_1=2$, $a_2=3$, $a_3=5$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m24s
Source on kvant.digital
Problem
Let $a_1$, $a_2$, $\ldots$, $a_n$ be distinct pairwise coprime positive integers. Prove that there exist infinitely many positive integers $b$ such that the numbers $b+a_1$, $b+a_2$, $\ldots$, $b+a_n$ are also pairwise coprime.
V. F. Lev
Exploration
Consider small examples of pairwise coprime numbers, such as $a_1=2$, $a_2=3$, $a_3=5$. The task is to find integers $b$ such that $b+2$, $b+3$, $b+5$ are pairwise coprime. Trial and error shows that $b=1$ works: $3,4,6$ are not all coprime, but $b=0$ gives $2,3,5$, which are coprime. For $b=6$, the numbers $8,9,11$ yield $\gcd(8,9)=1$, $\gcd(8,11)=1$, $\gcd(9,11)=1$, so it works. This suggests infinitely many solutions. The crucial insight is that the numbers $a_i$ are pairwise coprime, so any shared prime divisor among $b+a_i$ and $b+a_j$ must avoid the fixed primes dividing $a_i - a_j$. For each pair $(i,j)$, a prime dividing both $b+a_i$ and $b+a_j$ must divide $a_i - a_j$, which is a fixed integer. There are only finitely many such primes. Thus avoiding these finitely many primes modulo their product yields infinitely many $b$.
Problem Understanding
The problem asks to prove that given distinct pairwise coprime positive integers $a_1, \ldots, a_n$, there exist infinitely many positive integers $b$ such that $b+a_1, \ldots, b+a_n$ are also pairwise coprime. This is a Type D problem: we must construct $b$ explicitly or show that such $b$ exist infinitely often. The core difficulty is ensuring that no two of $b+a_i$ share a prime factor, knowing that any potential common prime factor must divide the difference $a_i - a_j$, which is fixed. The answer is that infinitely many $b$ exist because for each prime dividing any $a_i - a_j$, we can choose $b$ to avoid congruences that would force divisibility, and finitely many primes leave infinitely many congruence classes free.
Proof Architecture
Lemma 1: For any pair $(i,j)$ with $i \neq j$, if a prime $p$ divides both $b+a_i$ and $b+a_j$, then $p$ divides $a_i - a_j$. The proof is that $p \mid (b+a_i) - (b+a_j) = a_i - a_j$.
Lemma 2: For each pair $(i,j)$, the set of primes dividing $a_i - a_j$ is finite. This is immediate since each integer has finitely many prime divisors.
Lemma 3: Avoiding a finite set of primes via congruences modulo their product yields infinitely many integers $b$. The proof is by the Chinese Remainder Theorem: for each prime $p$, avoid the residue $-a_i \pmod{p}$ for any $i$, which is a finite restriction, leaving infinitely many integers satisfying all conditions.
Hardest direction: Ensuring that all $b+a_i$ are pairwise coprime simultaneously. Lemma 3 ensures that infinitely many $b$ avoid all forbidden congruences.
Solution
Let $P$ be the set of all primes dividing any difference $a_i - a_j$ with $i < j$. This set is finite. For each prime $p \in P$ and each $i$, the congruence $b \equiv -a_i \pmod{p}$ would make $p \mid b + a_i$. We wish to avoid common divisibility, so for each $p \in P$ and each pair $(i,j)$, we avoid $b$ satisfying $b \equiv -a_i \pmod{p}$ and $b \equiv -a_j \pmod{p}$ simultaneously. By Lemma 1, any prime dividing two of the $b+a_i$ must lie in $P$, so avoiding the above congruences guarantees that no prime divides more than one $b+a_i$.
Concretely, for each $p \in P$, select a residue class $r_p \pmod{p}$ avoiding all $-a_i \pmod{p}$ simultaneously. Since each $p$ divides at most one difference $a_i - a_j$, there is at least one residue modulo $p$ that avoids all conflicts. By the Chinese Remainder Theorem, there exist infinitely many integers $b$ satisfying $b \equiv r_p \pmod{p}$ for all $p \in P$. For such $b$, any prime dividing $b+a_i$ cannot divide $b+a_j$ for $i \neq j$, so $b+a_1, \ldots, b+a_n$ are pairwise coprime. This construction produces infinitely many $b$, completing the solution. ∎
Verification of Key Steps
Lemma 1 requires that $p \mid (b+a_i)$ and $p \mid (b+a_j)$ implies $p \mid a_i - a_j$. Subtracting yields $p \mid (b+a_i) - (b+a_j) = a_i - a_j$, which holds regardless of $b$.
Lemma 3 relies on the Chinese Remainder Theorem. The CRT guarantees a solution to a system of congruences modulo pairwise coprime moduli; even if the moduli are not coprime, the system is solvable provided all congruences are compatible. Here, we are only avoiding finitely many forbidden residues for each prime, which leaves nonempty residue classes for $b$ modulo each $p$, and hence infinitely many integers exist.
Testing small cases, such as $a_1=2$, $a_2=3$, $a_3=5$, $b=6$ gives $8,9,11$, which are pairwise coprime, confirming the method works concretely.
Alternative Approaches
An alternative method is probabilistic, observing that for large random $b$, the probability that two numbers $b+a_i$ share a prime factor from $P$ is less than 1, so infinitely many such $b$ exist. This approach is shorter but nonconstructive, as it does not produce an explicit sequence of $b$. The main approach is preferable because it is fully constructive and yields an explicit infinite set of admissible $b$ via the Chinese Remainder Theorem, making it rigorous and elementary, consistent with the style of Kvant.