Разделы 
Дополнительно
Задача по математике - 1974
2019-01-22 
Из промежутка $(2^{2n}, 2^{3n})$ выбрано $2^{2n-1} + 1$ нечетное число. Докажите, что среди выбранных чисел найдутся два, квадрат каждого из которых не делится на другое.
Решение:
Заметим, что среди выбранных чисел найдутся числа $а$ и $b$, имеющие одинаковые остатки отделения на $2^{2n}$. Докажем, что они - искомые.
Предположим, что $a^2 \vdots b$. Тогда и $(a - b)^2 = a^2 - 2ab + b^2 \vdots b$. Пусть $a = p \cdot 2^{2n} + r, b = q \cdot 2^{2n} + r$. Тогда $(p - q)^2 \cdot 2^{4n} \vdots b$, но поскольку $b$ - нечетное, то $(p - q)^2 \vdots b$, откуда $|p - q| > 2^n$ и $max(a, b) = max(p, q) \cdot 2^{2n} + r > 2^{3n}$, что невозможно по условию.
Из промежутка $(2^{2n}, 2^{3n})$ выбрано $2^{2n-1} + 1$ нечетное число. Докажите, что среди выбранных чисел найдутся два, квадрат каждого из которых не делится на другое.
Решение:
Заметим, что среди выбранных чисел найдутся числа $а$ и $b$, имеющие одинаковые остатки отделения на $2^{2n}$. Докажем, что они - искомые.
Предположим, что $a^2 \vdots b$. Тогда и $(a - b)^2 = a^2 - 2ab + b^2 \vdots b$. Пусть $a = p \cdot 2^{2n} + r, b = q \cdot 2^{2n} + r$. Тогда $(p - q)^2 \cdot 2^{4n} \vdots b$, но поскольку $b$ - нечетное, то $(p - q)^2 \vdots b$, откуда $|p - q| > 2^n$ и $max(a, b) = max(p, q) \cdot 2^{2n} + r > 2^{3n}$, что невозможно по условию.
