Maths Olympiad Prep

Track / Stage 7 / 49 of 300 #1449 of 1964

Problem 1449

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.1 Prove it

Let M M be a set of aritmetic progressions with integer terms and ratio bigger than 1 1.

a) Prove that the set of the integers Z \mathbb{Z} can be written as union of the finite number of the progessions from M M with different ratios.

b) Prove that the set of the integers Z \mathbb{Z} can not be written as union of the finite number of the progessions from M M with ratios integer numbers, any two of them coprime.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

### Part (a)
1. Define the Arithmetic Progressions:
Let M M be a set of arithmetic progressions with integer terms and ratio greater than 1. An arithmetic progression (AP) with ratio r r and initial term a a can be written as:
a,a+r,a+2r,a+3r, a, a + r, a + 2r, a + 3r, \ldots
where r>1 r > 1 and aZ a \in \mathbb{Z} .

2. Construct the Union:
We need to show that the set of integers Z \mathbb{Z} can be written as a union of a finite number of such progressions with different ratios. Consider the following progressions:
AP1:0,2,4,6,8,(ratio 2)AP2:1,3,5,7,9,(ratio 2) \begin{aligned} &\text{AP}_1: 0, 2, 4, 6, 8, \ldots \quad (\text{ratio } 2) \\ &\text{AP}_2: 1, 3, 5, 7, 9, \ldots \quad (\text{ratio } 2) \end{aligned}
These two progressions cover all integers. Specifically:
Z={0,2,4,6,}{1,3,5,7,} \mathbb{Z} = \{0, 2, 4, 6, \ldots\} \cup \{1, 3, 5, 7, \ldots\}
Here, the ratios are both 2, but the sequences are distinct and together cover all integers.

3. Conclusion:
Therefore, the set of integers Z \mathbb{Z} can be written as the union of a finite number of arithmetic progressions with different ratios.

### Part (b)
1. Assume the Existence of Such a Union:
Assume there exists a union of a finite number of arithmetic progressions from M M with integer ratios p1,p2,,pm p_1, p_2, \ldots, p_m , where any two of these ratios are coprime.

2. Form of the Progressions:
For each i i (where 1im 1 \le i \le m ), the terms of the progression with ratio pi p_i must have the form:
ain+bi a_i n + b_i
where ai a_i is the ratio and bi b_i is an integer.

3. Construct an Integer Not in Any Progression:
Consider an integer x x such that:
xbi+1(modai) x \equiv b_i + 1 \pmod{a_i}
for each i i . If such an x x exists, it does not belong to any of the m m progressions because it does not satisfy the form ain+bi a_i n + b_i for any i i .

4. Existence of Such an Integer:
Since any two of ai a_i are coprime, by the Chinese Remainder Theorem, there exists an integer x x that satisfies:
xbi+1(modai)for all i x \equiv b_i + 1 \pmod{a_i} \quad \text{for all } i
This x x is not in any of the progressions, contradicting the assumption that the union of the m m progressions covers Z \mathbb{Z} .

5. Conclusion:
Therefore, the set of integers Z \mathbb{Z} cannot be written as the union of a finite number of progressions from M M with integer ratios, any two of which are coprime.

\blacksquare

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.