Library / /20 of 48

, 2016

Number theory Difficulty 5.6 AIME, harder Prove it Baltic Way

Each sequence of at least two consecutive integers contains a number that is divisible by no prime number less than the amount of members in the sequence.

2. Each sequence of at least two consecutive integers contains a number that is relatively prime to all other members of the sequence.

Solution

Answer: Neither hypothesis is true.

1. The sequence $(2, 3, 4, 5, 6, 7, 8, 9)$ contains 8 consecutive integers which all are divisible by some prime less than 8.

2. By Chinese Remainder Theorem, there exists an integer $x$ that satisfies the following conditions:
* $x$ is divisible by $2$ , $5$ and $11$ ;
* $x + 16$ is divisible by $3$ , $7$ and $13$ .
Then the sequence $(x, x+1, \dots, x+16)$ contains 17 consecutive integers, each of which has a common prime factor with some other:

Number	Factors common to some other	Number	Factors common to some other
$x$	$2$ , $5$ , $11$	$x + 9$	$7$
$x + 1$	$3$	$x + 10$	$2$ , $3$ , $5$
$x + 2$	$2$ , $7$	$x + 11$	$11$
$x + 3$	$13$	$x + 12$	$2$
$x + 4$	$2$ , $3$	$x + 13$	$3$
$x + 5$	$5$	$x + 14$	$2$
$x + 6$	$2$	$x + 15$	$5$
$x + 7$	$3$	$x + 16$	$2$ , $3$ , $7$ , $13$
$x + 8$	$2$

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.