Kvant Math Problem 902

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m23s
Source on kvant.digital

Problem

The natural sequence 1, 2, 3, $\ldots$ has been partitioned into several arithmetic progressions. Prove that for at least one of these progressions, the first term is divisible by its common difference.

A. V. Kelarev

Exploration

Suppose the partition consists of finitely many arithmetic progressions

$$P_i={a_i,a_i+d_i,a_i+2d_i,\ldots}, \qquad d_i>0.$$

We must show that for some $i$, $d_i\mid a_i$.

Trying small examples suggests the statement is plausible. For instance,

$${1,3,5,\ldots}\cup{2,4,6,\ldots}$$

has first terms $1,2$ and common differences $2,2$; the second progression satisfies $2\mid2$.

A useful observation is that every progression contains infinitely many terms. Since only finitely many progressions are present, every sufficiently large integer belongs to exactly one of them.

To obtain a contradiction, assume that no progression has its first term divisible by its common difference. Then for every $i$,

$$a_i\not\equiv0\pmod{d_i}.$$

Hence each progression avoids the residue class $0\pmod{d_i}$.

The natural idea is to look at a common multiple

$$L=\operatorname{lcm}(d_1,\ldots,d_n).$$

Every multiple of $L$ is divisible by every $d_i$. Since $a_i\not\equiv0\pmod{d_i}$, no multiple of $L$ can belong to $P_i$. Indeed, all terms of $P_i$ are congruent to $a_i$ modulo $d_i$.

This would imply that no multiple of $L$ belongs to any progression, contradicting the fact that the progressions partition the positive integers.

The only point requiring careful justification is that every term of $P_i$ is congruent to $a_i$ modulo $d_i$.

Problem Understanding

The positive integers have been partitioned into finitely many arithmetic progressions. We must prove that at least one progression has first term divisible by its common difference.

This is a Type B problem, a pure proof problem.

The core difficulty is to exploit simultaneously the congruence classes determined by all common differences. The natural common modulus is the least common multiple of those differences.

Proof Architecture

Let the arithmetic progressions be $P_i={a_i+kd_i:k\ge0}$.

First lemma: every element of $P_i$ is congruent to $a_i\pmod{d_i}$; this follows directly from the definition of an arithmetic progression.

Second lemma: if $d_i\nmid a_i$, then no multiple of $d_i$ belongs to $P_i$; a multiple of $d_i$ is congruent to $0\pmod{d_i}$, whereas every element of $P_i$ is congruent to $a_i\not\equiv0\pmod{d_i}$.

Main step: let $L=\operatorname{lcm}(d_1,\ldots,d_n)$. If $d_i\nmid a_i$ for every $i$, then no multiple of $L$ belongs to any progression. Since the progressions partition the natural numbers, this is impossible because $L,2L,3L,\ldots$ are positive integers.

The most delicate point is proving that a multiple of $L$ cannot belong to any progression under the contradictory assumption.

Solution

Let the partition consist of the arithmetic progressions

$$P_i={a_i,a_i+d_i,a_i+2d_i,\ldots}, \qquad i=1,\ldots,n,$$

where $d_i>0$.

Assume, for contradiction, that none of these progressions has its first term divisible by its common difference. Then

$$d_i\nmid a_i$$

for every $i$.

Every term of $P_i$ has the form $a_i+kd_i$ with $k\ge0$. Hence

$$a_i+kd_i\equiv a_i \pmod{d_i}.$$

Therefore every element of $P_i$ is congruent to $a_i$ modulo $d_i$.

Since $d_i\nmid a_i$, we have

$$a_i\not\equiv0\pmod{d_i}.$$

Consequently no element of $P_i$ is divisible by $d_i$.

Now let

$$L=\operatorname{lcm}(d_1,\ldots,d_n).$$

Every multiple of $L$ is divisible by every $d_i$. In particular, if $m$ is a multiple of $L$, then

$$m\equiv0\pmod{d_i}$$

for every $i$.

Since every element of $P_i$ is congruent to $a_i\not\equiv0\pmod{d_i}$, the integer $m$ cannot belong to $P_i$. This is true for every $i=1,\ldots,n$.

Thus no multiple of $L$ belongs to any of the progressions $P_1,\ldots,P_n$.

But the progressions form a partition of the natural numbers, so every positive integer must belong to one of them. The positive integers

$$L,2L,3L,\ldots$$

are multiples of $L$, giving a contradiction.

The contradiction arose from the assumption that $d_i\nmid a_i$ for all $i$. Hence for at least one progression,

$$d_i\mid a_i.$$

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the congruence description of a progression. If

$$x=a_i+kd_i,$$

then

$$x-a_i=kd_i,$$

which is divisible by $d_i$. Hence $x\equiv a_i\pmod{d_i}$. No other residue class modulo $d_i$ can occur in $P_i$.

The second delicate step is the exclusion of multiples of $L$. Since $L$ is a common multiple of all $d_i$, every multiple $m=tL$ satisfies $m\equiv0\pmod{d_i}$. Under the contradictory assumption,

$$a_i\not\equiv0\pmod{d_i}.$$

Because all elements of $P_i$ are congruent to $a_i$ modulo $d_i$, the integer $m$ cannot lie in $P_i$. This argument must be carried out separately for each $i$.

The final contradiction uses only the definition of a partition. If an integer belongs to none of the progressions, the family cannot be a partition of the natural numbers. Since infinitely many multiples of $L$ exist, the contradiction is immediate.

Alternative Approaches

One may phrase the same argument in terms of residue classes. Each progression $P_i$ occupies exactly one residue class modulo $d_i$, namely $a_i\bmod d_i$. If $a_i\not\equiv0\pmod{d_i}$, then the residue class $0\bmod d_i$ is completely absent from $P_i$. Choosing $L$ as the least common multiple of all common differences, every multiple of $L$ lies simultaneously in the residue class $0\bmod d_i$ for every $i$, so none can belong to any progression.

Another formulation uses the Chinese Remainder viewpoint. The multiples of $L$ form a nonempty intersection of the residue classes $0\bmod d_i$. Under the assumption $a_i\not\equiv0\pmod{d_i}$ for all $i$, every progression misses that intersection. The partition property is then violated. The main proof is preferable because it avoids introducing any machinery beyond elementary congruences and least common multiples.