Maths Olympiad Prep

Library / /44 of 152

Number theory Difficulty 5.8 AIME, harder Prove it Russia

A positive integer is called good if it has exactly two different prime divisors. Determine whether there exist 18 consecutive positive integers all of which are good. (O. Podlipsky)

Solution

Ответ. Не могут.

Предположим, что нашлись 18 хороших чисел подряд. Среди них найдутся три числа, делящихся на 66. Пусть это числа 6n6n, 6(n+1)6(n+1) и 6(n+2)6(n+2). Поскольку эти числа — хорошие, и в разложение каждого из них на простые множители входят двойка и тройка, других простых делителей у них быть не может.

Далее, лишь одно из трёх подряд идущих натуральных чисел nn, n+1n+1, n+2n+2 может делиться на 33. Значит, остальные два являются степенями двойки. Но пары степеней двойки, отличающихся не более чем на два — это только (1,2)(1,2) и (2,4)(2,4); поэтому n2n \le 2. Однако тогда среди наших 18 чисел есть простое число 1313 (так как 6n136(n+2)6n \le 13 \le 6(n+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.