Library / /3 of 22

, 2014

Number theory Difficulty 4.6 AIME Prove it Romania

Given any integer $n \ge 2$ , show that there exists a set of $n$ pairwise coprime composite integers in arithmetic progression.

Solution

Fix a prime $p > n$ and an integer $N \ge p + (n-1)n!$ and consider the arithmetic progression of length $n$ consisting of $N! + p + kn!$ , $k = 0, 1, \dots, n-1$ .

Suppose, if possible, that $q$ is a prime factor of two of these numbers. Then $q$ divides their difference which is of the form $kn!$ , for some positive integer $k < n$ . It follows that $q$ does not exceed $n$ , so $n!$ and $N!$ are both divisible by $q$ , and consequently so is $p$ — a contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.