Иван выбрал натуральное число k и написал очень длинное произведение (1+2)⋅(1+2+3)⋅…⋅(1+2+3 + ...+ 111)⋅k. Результат этого произведения оказался квадратом натурального числа.…

Задача: найти наименьшее k such that произведение ∏_{n=1}^{111} (1+2+...+n) умноженное на k является квадратом натурального числа.

1. Преобразование выражения

• Поскольку сумма 1+2+...+n равна n(n+1)/2, произведение равно P = ∏_{n=1}^{111} [n(n+1)/2].
• Разделим множители на числители и знаменатели: ∏_{n=1}^{111} n(n+1) = (1·2)(2·3)(3·4)...(111·112) = (111)! · (112)!.
• Следовательно, P = (111)! · (112)! / 2^{111}.

2. Параметризация по простым и их показатель степеней Пусть e_p — экспонента простого p в факторизации P. Нам важна параллель по модулю 2 (паритет).

• Общее выражение: e_p = v_p((111)!) + v_p((112)!) − 111·[p=2], где [p=2] равно 1, если p=2, иначе 0.

• Замечаем, что (112)! = 112 · (111)!, значит v_p((112)!) = v_p(112) + v_p((111)!). Тогда e_p = v_p((111)!) + [v_p(112) + v_p((111)!)] − 111·[p=2] = 2·v_p((111)!) + v_p(112) − 111·[p=2].

• Так как 2·v_p((111)!) чётно, то паритет e_p зависит только от v_p(112) и от −111·[p=2].

3. Обратим внимание на отдельные пробы

• Разложим 112: 112 = 2^4 · 7.
• Для нечётных простых p: v_p(112) = 0, следовательно e_p ≡ 0 (мод 2). Значит все нечётные простые кроме того, что делят 112, дают чётные степени в P. Единственный нечётный простый с ненулевой степени — это p = 7, где v_7(112) = 1, следовательно e_7 ≡ 1 (мод 2). То есть 7 встречается в P с нечётной степенью.
• Для p = 2: e_2 ≡ v_2(112) − 111 (мод 2) = 4 − 111 (мод 2) = −107 (мод 2) = 1 (мод 2). Значит 2 также встречается с нечётной степенью в P.

Итого: в P нечётные степени имеют исключительно пробы 2 и 7. Все остальные пробы чётны.

4. Нужное k Чтобы k·P была квадратом, нужно, чтобы после умножения все экспоненты стали чётными. Это означает:

• v_2(k) должен быть нечётной (чтобы привести e_2 к чётному),
• v_7(k) должен быть нечётной (чтобы привести e_7 к чётному),
• для всех других p достаточно, чтобы v_p(k) было чётным (то есть для них k не обязателен).

Наименьшее такое k — это произведение простых 2 и 7 без дополнительных множителей: k = 2 · 7 = 14.

Ответ: 14.