D10 p-адическое v_p и формула Лежандра

Метод состоит в точном подсчёте количества раз, которое простое $p$ делит заданное целое число. Функция $v_p(n)$ (называемая $p$-адическим показателем или $p$-адической оценкой) возвращает наибольший показатель $k$, при котором $p^k \mid n$. Например, $v_2(24) = 3$, $v_3(18) = 2$.

Интуиция: каждое натуральное число можно представить как бесконечный вектор $(v_2(n), v_3(n), v_5(n), v_7(n), \ldots)$ по всем простым. Умножение чисел соответствует сложению этих векторов. Это как система счисления, только вместо цифр — показатели простых. Задачи о делимости становятся задачами о компонентах этих векторов.

Формула Лежандра отвечает на вопрос: сколько раз $p$ делит $n!$? Ответ: $v_p(n!) = \sum_{k=1}^{\infty} \lfloor n/p^k \rfloor$. На олимпиадах формула Лежандра нужна в задачах про факториалы, биномиальные коэффициенты, и любые выражения с $n!$.

• Мультипликативность $v_p$: $v_p(ab) = v_p(a) + v_p(b)$ для любых целых $a, b \neq 0$. Условие: всегда. Когда использовать: при разложении произведения на множители — $v_p$ каждого множителя складывается.

• Формула Лежандра: $v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor = \frac{n - s_p(n)}{p - 1}$, где $s_p(n)$ — сумма цифр $n$ в $p$-ичной записи. Условие: $p$ простое, $n$ натуральное. Когда использовать: при любых вопросах о делимости факториала, числе нулей в $n!$, и биномиальных коэффициентах.

• Ультраметрическое неравенство: $v_p(a + b) \geq \min(v_p(a), v_p(b))$; равенство при $v_p(a) \neq v_p(b)$. Когда использовать: при оценке $v_p$ суммы двух чисел с разными $p$-адическими показателями.

• Биномиальный коэффициент (теорема Кумера): $v_p\binom{m+n}{m} = \frac{s_p(m) + s_p(n) - s_p(m+n)}{p-1} \geq 0$. Когда использовать: при задачах о делимости биномиальных коэффициентов.

• Применение формулы Лежандра к факториалу. Для конкретного $n$ и $p$ вычисли $\lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \lfloor n/p^3 \rfloor + \ldots$ — серия конечна.

• Число нулей в $n!$. Последних нулей в десятичной записи $n!$ ровно $v_5(n!) = \lfloor n/5 \rfloor + \lfloor n/25 \rfloor + \lfloor n/125 \rfloor + \ldots$ (поскольку $v_2(n!) > v_5(n!)$ всегда).

• Анализ биномиального коэффициента. $v_p\binom{n}{k} = v_p(n!) - v_p(k!) - v_p((n-k)!)$ — примени формулу Лежандра к каждому факториалу.

• Разложение выражения через $v_p$. Если задача содержит НОД и НОК: $v_p(\gcd(a,b)) = \min(v_p(a), v_p(b))$, $v_p(\text{lcm}(a,b)) = \max(v_p(a), v_p(b))$.

• Точное условие делимости через $v_p$. $a \mid b$ равносильно $v_p(a) \leq v_p(b)$ для всех простых $p$.

Поверхностные признаки (что буквально написано):
- «Сколько нулей стоит в конце числа $n!$?»
- «На какую наибольшую степень $p$ делится $\binom{n}{k}$?»
- «Докажите, что $\binom{2n}{n}$ делится на $p$ для простого $p \leq 2n$»
- «Найдите $v_p(n!)$» или «при каком наибольшем $k$ выражение делится на $p^k$?»

Структурные признаки (форма выражения, объекты):
- В задаче есть факториалы, биномиальные коэффициенты, или НОД/НОК
- Вопрос о «наибольшей степени», на которую делится число — это $v_p$ - Произведение нескольких последовательных чисел

Цель задачи (что от тебя хотят):
- Точно подсчитать степень делимости факториала или биномиального коэффициента
- Найти наибольшее $k$ такое, что $p^k \mid f(n)$ - Сравнить степени делимости двух выражений

Задача 1. Сколько нулей стоит в конце числа $100!$ (в десятичной записи)?

Источник: ВсОШ, муниципальный этап, стандартный тип

Как думать (рассуждение ученика$):
1. $Что вижу?* Количество нулей в конце $= v_{10}(100!) = \min(v_2(100!), v_5(100!))$. Поскольку $v_2 > v_5$ всегда, достаточно найти $v_5(100!)$.$2. *$Применяю формулу Лежандра: $v_5(100!) = \lfloor 100/5 \rfloor + \lfloor 100/25 \rfloor + \lfloor 100/125 \rfloor = 20 + 4 + 0 = 24$.

Решение:

Каждый ноль в конце $100!$ соответствует множителю $10 = 2 \cdot 5$. Поскольку $v_2(100!) > v_5(100!)$, число нулей равно $v_5(100!)$.

По формуле Лежандра:$$v_5(100!) = \left\lfloor \frac{100}{5} \right\rfloor + \left\lfloor \frac{100}{25} \right\rfloor + \left\lfloor \frac{100}{125} \right\rfloor = 20 + 4 + 0 = 24.$$

Ответ: $24$ нуля.

Что в этой задаче было главным: формула Лежандра применяется напрямую, нулей дают именно пятёрки (двоек всегда больше).

Задача 2. При каком наибольшем натуральном $k$ число $\binom{200}{100}$ делится на $3^k$?

Источник: ВсОШ заключительный этап, тренировочная

Как думать (рассуждение ученика$):
1. $Что вижу?* $v_3\binom{200}{100} = v_3(200!) - 2 \cdot v_3(100!)$. Применяю формулу Лежандра.$2. *$Вычисляю $v_3(200!):$ $\lfloor 200/3 \rfloor + \lfloor 200/9 \rfloor + \lfloor 200/27 \rfloor + \lfloor 200/81 \rfloor + \lfloor 200/243 \rfloor = 66 + 22 + 7 + 2 + 0 = 97$.$3. *$Вычисляю $v_3(100!):$ $\lfloor 100/3 \rfloor + \lfloor 100/9 \rfloor + \lfloor 100/27 \rfloor + \lfloor 100/81 \rfloor = 33 + 11 + 3 + 1 = 48$.$4. *$Ответ: $97 - 2 \cdot 48 = 97 - 96 = 1$.

Решение:

$$v_3\binom{200}{100} = v_3(200!) - 2v_3(100!).$$ $$v_3(200!) = \left\lfloor \frac{200}{3} \right\rfloor + \left\lfloor \frac{200}{9} \right\rfloor + \left\lfloor \frac{200}{27} \right\rfloor + \left\lfloor \frac{200}{81} \right\rfloor = 66 + 22 + 7 + 2 = 97.$$ $v_3(100!) = 33 + 11 + 3 + 1 = 48.$ $v_3\binom{200}{100} = 97 - 96 = 1.$

Ответ: $k = 1$.

Что в этой задаче было главным: формула $v_p\binom{m+n}{m} = v_p((m+n)!) - v_p(m!) - v_p(n!)$ и аккуратное применение Лежандра к каждому факториалу.

• Ошибка: считать количество нулей в $n!$ просто как $\lfloor n/10 \rfloor$. → Почему неверно: это подсчёт кратных $10$, но кратные $25$, $125$ дают дополнительные пятёрки. → Как избежать: всегда применяй полную формулу Лежандра со всеми степенями $p$.

• Ошибка: забыть, что $v_p(a/b)$ корректна только если $b \mid a$. → Почему неверно: $v_p$ определено для целых чисел, не для произвольных дробей. → Как избежать: при работе с дробями всегда убеждайся, что числитель делится на знаменатель.

• Ошибка: не досчитать слагаемые в формуле Лежандра (остановиться на $\lfloor n/p^2 \rfloor$). → Почему неверно: $\lfloor n/p^3 \rfloor$ может быть ненулевым. → Как избежать: добавляй слагаемые, пока $p^k \leq n$.

• Ошибка: $v_p(a + b) = v_p(a) + v_p(b)$ (перепутать умножение и сложение). → Почему неверно: аддитивность $v_p$ — только для умножения! Для суммы: $v_p(a+b) \geq \min(v_p(a), v_p(b))$. → Как избежать: запомни: $v_p$ мультипликативна (складывается при умножении), но не аддитивна.