Задача 109773
|
|
 |
Условие
Из промежутка (22n, 23n) выбрано 22n–1 + 1 нечётное число.
Докажите, что среди выбранных чисел найдутся два, квадрат каждого из которых не делится на другое.
Решение
Заметим, что среди выбранных чисел найдутся числа a и b, имеющие одинаковые остатки от деления на 22n. Докажем, что они – искомые. Предположим, что a² делится на b. Тогда на b делится и (a – b)² = a² – 2ab + b². Пусть a = p·22n + r, b = q·22n + r. Тогда (p – q)²·24n делится на b, но поскольку b нечётно, то (p – q)² делится на b, откуда |p – q| > 2n и max {a, b} = max {p, q}·22n + r > 23n, что невозможно.
