Задание олимпиады: степень факториала простого p в факториале квадрата p – олимпиадная задача по теории чисел

  Если (p²)! кратно (p!)ⁿ, то  n ≤ p + 1,  так как p входит в разложение числа p! на простые множители в степени 1 (а значит, в разложение числа (p!)ⁿ – в степени n), а в разложение числа (p²)! – в степени  p + 1.   Докажем, что (p²)! делится на  (p!)^p+1.   Первый способ. Запишем p² различных элементов в виде таблицы p×p. Всего таких таблиц (p²)!. Две таблицы назовём эквивалентными, если одна получается из другой некоторыми перестановками элементов внутри строк, а также некоторой перестановкой самих строк (всего  p + 1  перестановка p объектов). В каждом классе эквивалентности (p!)^p+1 таблиц. Поэтому (p²)! делится на (p!)^p+1.   Второй способ.     кратно p!, так как     кратно k при всех  k ≤ p.   Третий способ. Возьмём произвольное простое число  q ≤ p  и докажем, что в разложение числа (p!)^p+1 на простые множители оно входит в степени, не большей, чем в разложение числа (p²)!.

  Пусть  qⁿ ≤ p < qⁿ⁺¹,  тогда  q²ⁿ ≤ p² < q²ⁿ⁺².  По формуле Лежандра (см. задачу 160553) достаточно проверить, что

p + 1.