Задача 111927

Темы:    [ Произведения и факториалы ] [ Треугольник Паскаля и бином Ньютона ] [ Простые числа и их свойства ] [ Основная теорема арифметики. Разложение на простые сомножители ] [ Разбиения на пары и группы; биекции ]

Сложность: 5- Классы: 9,10,11

Условие

Автор: Канунников А.Л.

Для каждого простого p найдите наибольшую натуральную степень числа 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²ⁿ⁺².  По формуле Лежандра (см. задачу 60553) достаточно проверить, что

  Из очевидного неравенства  k[x] ≤ [kx]  следует, что  

  Кроме того,  

Ответ

p + 1.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	72
Год	2009
класс
Класс	11
задача
Номер	5