Задача 78652

Темы:    [ НОД и НОК. Взаимная простота ] [ Простые числа и их свойства ] [ Доказательство от противного ]

Сложность: 3+ Классы: 8,9

Условие

Доказать, что для любых трёх чисел, меньших 1000000, найдётся число, меньшее 100 (но большее 1), взаимно простое с каждым из них.

Решение

Составим сначала список простых чисел, меньших 100:  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 78, 83, 89, 97. Предположим, что на каждое из этих чисел делится хотя бы одно из трёх данных чисел a, b, c. Тогда  abc ≥ 2·3·5·...·97 > 10¹⁸.  Но  a, b, c ≤ 10⁶,  поэтому  abc ≤ 10¹⁸.  Противоречие.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	31
Год	1968
вариант
	1
Класс	7
Тур	1
задача
Номер	3