Question

Найдите наибольшее натуральное число n, для которого произведение чисел n, n+1, n+2,..., n+20 делится на квадрат одного из них.

Answer 1

$\prod_{i=0}^{20}{n+i}\equiv 0\pmod{(n+20)^2} \Rightarrow \prod_{i=0}^{19}{n+i}\equiv 0\pmod{(n+20)}$

Если $n+20$ имеет простые делители $d_1, d_2\ldots,d_k$, то мы хотим максимизировать показатели простых чисел при факторизации $n+20$. Любой $d_i < 20, i\in\{1,2\ldots{k}\}$, начиная с $d_i\mid{n+20}$, и другой $n+r$, где $r\in\{1,2\ldots,19\}$ имеет множитель $d_i,$ поэтому $20-d_i=r\Rightarrow d_i < 20$

Пусть $p < 20$ — простое число. Обратите внимание, что $\max{\nu_p{\left (\prod_{i=0}^{19}{n+i} \right )}}=\sum_{i=1}^{s}{\left \lfloor \frac{20}{p^s} \right \rfloor},$

где $p^s\leq20\leq{p^{s+1}}$. Это легко вывести, если мы допустим $p\mid{n+20}$ и найдем степени $p$ в значении $\prod_{i=0}^{19}{n+i}\equiv \prod_{i=1}^{20}{i} \pmod{p}$. Проверяем все $p < 20$ и делим $n+20$ на все простые числа меньше 20 (чтобы максимизировать его), максимально возможное значение $n=2^{18}\cdot3^8\cdot5^4\cdot7^2\cdot11\cdot13\cdot17\cdot19$