Оценка + пример в задачах по теории чисел

Рассмотрим произвольное число не превосходящее Представим в виде где — число, свободное от квадрата или равное (будем говорить, что имеет свободное от квадрата число ).

Покажем, что если два числа и в произведении дают квадрат и имеют свободные от квадрата числа и то Пусть это не так. Тогда либо существует такое простое число что не кратно а — кратно или наоборот. Но в таком случае входит в разложение в чётной степени, а в разложение — в нечётной или наоборот. Следовательно, не квадрат, противоречие.

Из вышеописанных рассуждений также следует, что если и — квадраты, то — также квадрат.

Теперь ясно, что все числа от до разбиваются на группы чисел с одинаковым свободным от квадрата числом. То есть любые два числа из одной группы в произведении дают квадрат, а любые два из разных — не дают.

Узнаем количество чисел в самой большой группе. Числа из произвольной группы в порядке возрастания выглядят так: — свободное от квадрата или равное В силу упорядочивания но тогда количество чисел в группе не превосходит

Найдём максимальное значение Мы знаем, что откуда Таким образом,

Значит, количество чисел в самой большой группе не больше Такая группа есть: Значит, нам хватит цветов, потому что мы можем в каждой группе раскрасить числа в разные цвета. Если же количество цветов меньше то в самой большой группе будут два числа одного цвета.