Kvant Math Problem 167

Consider an arithmetic progression $a$, $a+d$, $a+2d$, $\dots$, where $a$ and $d$ are natural numbers.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m16s
Source on kvant.digital

Problem

Prove that in any arithmetic progression $a$, $a+d$, $a+2d$, $\ldots$, $a+nd$, $\ldots$ consisting of natural numbers, there exist infinitely many terms whose prime factorization involves exactly the same prime numbers.

G. Pólya

Exploration

Consider an arithmetic progression $a$, $a+d$, $a+2d$, $\dots$, where $a$ and $d$ are natural numbers. Each term has a unique prime factorization. The claim is that infinitely many terms share exactly the same set of prime factors.

Begin with small examples. Take $a = 6$ and $d = 4$. The progression is $6, 10, 14, 18, 22, 26, 30, 34, 38, 42, \dots$. Examine prime factors:

  • $6 = 2 \cdot 3$,
  • $10 = 2 \cdot 5$,
  • $14 = 2 \cdot 7$,
  • $18 = 2 \cdot 3^2$,
  • $22 = 2 \cdot 11$,
  • $26 = 2 \cdot 13$,
  • $30 = 2 \cdot 3 \cdot 5$,
  • $34 = 2 \cdot 17$,
  • $38 = 2 \cdot 19$,
  • $42 = 2 \cdot 3 \cdot 7$.

We notice that $6$ and $18$ share the same set of prime factors ${2,3}$, differing only in powers. Similarly, $30$ and $42$ share the set ${2,3,5,7}$, if we extend the progression. The crucial insight is that the difference $d$ determines a "stabilization" modulo certain multiples.

The hard point is proving this works for any arithmetic progression, not just the small example. How to guarantee infinitely many terms with the same prime support? A key is to focus on primes dividing $d$. Terms far along in the sequence can be made multiples of some factorization involving only primes dividing $d$ and a fixed finite set of primes from early terms.

The likely mechanism uses Dirichlet's theorem on arithmetic progressions, or more elementary, the Chinese remainder theorem combined with multiplicativity, to construct infinitely many terms divisible only by prescribed primes.

Problem Understanding

The problem asks to prove that in any arithmetic progression of natural numbers, there are infinitely many terms whose prime factors belong to the same finite set. The progression is $a + nd$ with $n \ge 0$. This is a Type B problem, "Prove that".

The core difficulty is showing that no matter how $a$ and $d$ are chosen, some infinite subset of terms repeats exactly the same set of primes in its factorization. The intuition is that primes dividing $d$ appear repeatedly in a controlled way, and other primes in $a$ can be stabilized via multiples. This stabilization produces infinitely many terms sharing the same prime set.

Proof Architecture

Lemma 1. For any finite set of primes, there exists a natural number divisible only by these primes. Sketch: use their powers to construct products.

Lemma 2. For an arithmetic progression $a + nd$, the set of prime divisors of $d$ appears in all differences of consecutive terms. Sketch: consecutive differences are $d$, so any prime in $d$ occurs in the difference, not necessarily in every term but can be controlled via congruences.

Lemma 3. There exists an index $n_0$ such that $a + n_0 d$ is divisible only by primes from a prescribed finite set including all primes dividing $a$ and $d$. Sketch: choose $n_0$ as a multiple of a product of the primes dividing $a$ and $d$; Chinese remainder theorem ensures the term has exactly that prime support.

Lemma 4. Multiplying $n_0$ by suitable powers of primes in $d$ generates infinitely many terms with identical prime sets. Sketch: using multiplicativity, increasing powers of primes in $d$ does not introduce new primes.

The hardest part is Lemma 4, ensuring no extra primes appear as exponents grow; this step must be rigorous.

Solution

Let $P$ be the set of all primes dividing $a$ and $d$. This set is finite. Consider a term $a + nd$. Any prime not in $P$ occurs only finitely many times among terms, because if $p$ divides $a + nd$ for some $n$, then $p$ divides the difference of terms, which is $d$, and $p \mid d$, contradiction. Therefore, all primes dividing infinitely many terms are in $P$.

Construct a term $A = a + n_0 d$ divisible only by primes in $P$. Since $a$ and $d$ are finite, such an $n_0$ exists: for each $p \in P$, take a sufficiently large exponent so that $p^{k_p} \mid a + n_0 d$ without introducing new prime factors. Chinese remainder theorem ensures a simultaneous solution $n_0$.

Now consider the sequence $A, A + d', A + 2d', \dots$, where $d' = \prod_{p \in P} p^{m_p}$ for sufficiently large $m_p$ to preserve the prime set. Multiplying or adding multiples of $d'$ does not introduce new primes outside $P$. Therefore, the prime factorization set remains exactly $P$ across this subsequence.

Since $n$ can be taken arbitrarily large in $n_0 + k d'$, this produces infinitely many terms sharing exactly the same prime set. This completes the proof.

∎

Verification of Key Steps

The delicate step is proving no new primes appear when forming the subsequence $A + k d'$. Suppose $q$ is a prime dividing $A + k d'$. Then $q \mid A + k d' - A = k d'$, so $q$ divides $d'$. By construction $d'$ is a product of primes in $P$. Thus $q \in P$. No other prime can appear.

Another subtle step is constructing $A$ such that all primes outside $P$ are excluded. Since each prime not in $P$ divides only finitely many terms, taking $n_0$ larger than all these finitely many indices guarantees $a + n_0 d$ is free from outside primes.

Alternative Approaches

A more advanced approach uses Dirichlet's theorem on arithmetic progressions, which ensures infinitely many primes in any progression with $\gcd(a,d)=1$. One can then partition the progression modulo products of primes in $P$ to find terms with fixed prime support. The elementary method above is preferable because it avoids deep results in analytic number theory and relies only on basic divisibility and the Chinese remainder theorem.