Задача
NT-B1-M08-P024 Последовательные несвободные от квадратов числа
Докажите, что для любого \(k\ge1\) существуют \(k\) последовательных натуральных чисел, каждое из которых делится на квадрат некоторого простого числа.
Выберите разные простые \(p_1,\ldots,p_k\) и задайте \(n+i\equiv0\pmod{p_i^2}\).
Выберем попарно различные простые \(p_1,\ldots,p_k\). Рассмотрим систему \(n\equiv-1\pmod{p_1^2}\), \(n\equiv-2\pmod{p_2^2}\), \(\ldots\), \(n\equiv-k\pmod{p_k^2}\). Модули \(p_i^2\) попарно взаимно просты, поэтому по CRT существует решение \(n_0\). Тогда для каждого \(i\) число \(n_0+i\) делится на \(p_i^2\), то есть не является свободным от квадратов. Прибавляя к \(n_0\) кратные произведения \(p_1^2\cdots p_k^2\), можно выбрать положительное \(n\). Значит, такие \(k\) последовательных чисел существуют.
Сильная конструкция: CRT используется не для вычисления, а для создания заданного свойства.