Часто в математических кружках дают задачу определить, на сколько нулей заканчивается число 100!.
(Восклицательный знак означает факториал. В частности, 100!=1*2*3*...*99*100, т.е. произведение натуральных чисел от 1 до 100.)
Школьникам надо заметить, что число заканчивается на k или больше нулей, если в его разложении на множители входит минимум k двоек и минимум k пятёрок.
Следующим продвижением будет соображение, что пятёрки встречаются реже, поэтому надо определить, на какую максимальную степень пятёрки делится 100!.
Пятёрки входят в числа, кратные пяти (не очень неожиданно, правда?). Их ровно 100/5=20.
Задача решена?
А вот и нет! Ведь есть числа 25, 50, 75, 100, в которые пятёрка входит аж два раза!
А три раза пятёрка входит в 5^3=125, но никак не раньше.
Поэтому ответ на вопрос первой задачи - 100/5+100/25=20+4=24.
Теперь давайте попытаемся немного обобщить задачу и ответить на вопрос, на какую максимальную степень простого числа p делится n! (напомню, что число называется простым, если оно делится только на единицу и на само себя).
На p делится каждое p-е число. А их ровно [n/p] ([x] означает целую часть числа x, т.е. минимальное целое число, не превосходящее x.)
Зачем нужна целая часть? Ну, например 100 на 23 не делится. Поэтому, 23 как множитель входит только в числа 23, 46, 69, 92. По другому, [100/23]=4.
Но ведь, как и в задаче про 100!, число p может входить в числа p^2, 2p^2, 3^2, ...
Сколько таких чисел? А их ровно [n/p^2].
Аналогично, три раза число p входит в разложение n! ровно [n/p^3] раз и т.д.
Таким образом, мы доказали формулу Лагранжа:
ord(n!,p)=[n/p]+[n/p^2]+[n/p^3]+...
Здесь ord(n!,p) означает степень вхождения простого числа p в n!.
Кажется, что ничего сложного?
Но эта формула решает задачу не только из моего поста про постулат Бертрана, но и задачу с последней Международной математической олимпиады школьников!
Решите в натуральных числах уравнение
k!=(2^n-1)(2^n-2)(2^n-4)*...*(2^n-2^(n-1)).
Справитесь?
