Глава
Теория
\(v_p(n)\) - это показатель простого \(p\) в разложении числа \(n\). Вместо того чтобы спрашивать «делится ли число», мы спрашиваем «сколько раз оно делится на \(p\)». Это превращает задачи о степенях простых, факториалах и биномиальных коэффициентах в точные вычисления.
Если \(p\) простое, то \(v_p(ab)=v_p(a)+v_p(b)\), \(v_p(a^k)=k v_p(a)\). Для факториала используется формула Лежандра: \(v_p(n!)=\lfloor n/p \rfloor+\lfloor n/p^2 \rfloor+\lfloor n/p^3 \rfloor+\cdots\). Количество нулей \(n!\) в десятичной записи равно \(v_5(n!)\), потому что двоек больше, чем пятёрок.
Valuations нужны, когда спрашивают максимальное \(k\), для которого \(p^k\mid N\), когда есть факториалы, произведения подряд идущих чисел, биномиальные коэффициенты, последние нули или делимость на составное число вида \(2^a3^b5^c\).
Слова «наибольшая степень», «сколько нулей», «делится на \(m^k\)», «найдите показатель простого» почти всегда указывают на \(v_p\). Если число составное, разложите его на простые и возьмите минимум по ограничениям.
Нельзя считать только множители, кратные \(p\): множители, кратные \(p^2\), дают дополнительный вклад. В десятичных нулях ограничивает число пятёрок, а не двоек. Для \(m^k\mid N\), где \(m\) составное, нужно учитывать все простые делители \(m\).
1. Какое простое \(p\) важно? 2. Нужно ли разложить модуль на простые? 3. Для факториала применена ли формула Лежандра со всеми степенями \(p\)? 4. Для составного основания взят ли минимум? 5. Проверено ли, что найденная степень действительно максимальна?
Примеры
Учит читать разложение числа.
Задача. Найдите \(v_2(72)\) и \(v_3(72)\).
Имеем \(72=2^3\cdot3^2\). Поэтому \(v_2(72)=3\), а \(v_3(72)=2\).
Комментарий. Это не количество делителей, а показатель конкретного простого.
Показывает, как считать показатель простого в факториале.
Задача. Найдите \(v_3(100!)\).
По формуле Лежандра \(v_3(100!)=\lfloor100/3\rfloor+\lfloor100/9\rfloor+\lfloor100/27\rfloor+\lfloor100/81\rfloor=33+11+3+1=48\).
Комментарий. Множители, кратные \(9\) и \(27\), дают дополнительные тройки.
Связывает valuations с записью числа.
Задача. Сколько нулей в конце числа \(100!\)?
Количество нулей равно числу множителей \(10=2\cdot5\). В факториале двоек больше, поэтому считаем пятёрки: \(v_5(100!)=20+4=24\). Ответ: \(24\).
Комментарий. Для десятичной записи почти всегда ограничивают пятёрки.
Учит брать минимум по простым делителям.
Задача. Найдите наибольшее \(k\), для которого \(12^k\mid100!\).
Так как \(12=2^2\cdot3\), нужно \(2k\le v_2(100!)\) и \(k\le v_3(100!)\). Имеем \(v_2(100!)=50+25+12+6+3+1=97\), \(v_3(100!)=48\). Поэтому \(k\le48\) по двойкам и \(k\le48\) по тройкам. Ответ: \(48\).
Комментарий. Составное основание всегда раскладываем.
Показывает valuation для дроби с факториалами.
Задача. Найдите \(v_2\left(\binom{16}{6}\right)\).
Используем \(\binom{16}{6}=16!/(6!10!)\). Тогда \(v_2(16!)=8+4+2+1=15\), \(v_2(6!)=3+1=4\), \(v_2(10!)=5+2+1=8\). Значит, \(v_2\left(\binom{16}{6}\right)=15-4-8=3\).
Комментарий. Для биномиальных коэффициентов показатели вычитаются.
Показывает, что база может быть не десятичной.
Задача. Сколько нулей в конце \(100!\) в системе счисления с основанием \(12\)?
Основание \(12=2^2\cdot3\). Нужно найти максимум \(k\), для которого \(12^k\mid100!\). Из примера: \(v_2(100!)=97\), \(v_3(100!)=48\). Значит, \(k=\min(\lfloor97/2\rfloor,48)=48\).
Комментарий. Задача та же, что и про \(12^k\mid100!\), но в другой оболочке.
Готовит к доказательным задачам.
Задача. Докажите, что для любого \(n\ge1\) число \(n!\) не делится на \(2^n\).
По формуле Лежандра \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots\). Каждое слагаемое строго меньше соответствующего члена геометрической суммы \(n/2+n/4+\cdots=n\). Поэтому \(v_2(n!)
Комментарий. Оценка суммы floors часто проще точного значения.
Олимпиадная идея: доказать делимость через \(v_p\).
Задача. Докажите, что произведение любых \(n\) последовательных целых чисел делится на \(n!\).
Пусть произведение равно \(A=(m+1)(m+2)\cdots(m+n)\). Для любого простого \(p\) нужно доказать \(v_p(A)\ge v_p(n!)\). Среди \(n\) последовательных чисел как минимум \(\lfloor n/p\rfloor\) делятся на \(p\), как минимум \(\lfloor n/p^2\rfloor\) делятся на \(p^2\), и так далее. Поэтому \(v_p(A)\ge\sum_i\lfloor n/p^i\rfloor=v_p(n!)\). Это верно для всех простых \(p\), значит \(n!\mid A\).
Комментарий. Это доказательство эквивалентно целочисленности биномиального коэффициента.
Задачи
Найдите \(v_2(72)\).
Разложите \(72\) на простые множители.
\(72=2^3\cdot3^2\), поэтому \(v_2(72)=3\).
Найдите \(v_5(1000)\).
Используйте \(1000=10^3\).
\(1000=2^3\cdot5^3\). Поэтому \(v_5(1000)=3\).
Найдите \(v_3(50!)\).
Сложите \(\lfloor50/3\rfloor+\lfloor50/9\rfloor+\lfloor50/27\rfloor\).
По формуле Лежандра \(v_3(50!)=16+5+1=22\).
Сколько нулей в конце \(80!\) в десятичной записи?
Считайте пятёрки.
Количество нулей равно \(v_5(80!)=\lfloor80/5\rfloor+\lfloor80/25\rfloor=16+3=19\).
Найдите наибольшее \(k\), для которого \(2^k\mid100!\).
Это \(v_2(100!)\).
\(v_2(100!)=50+25+12+6+3+1=97\). Значит, наибольшее \(k\) равно \(97\).
Найдите \(v_2(2026!)\).
Сложите целые части деления на \(2,4,8,\ldots\).
\(v_2(2026!)=1013+506+253+126+63+31+15+7+3+1=2018\).
Найдите наибольшее \(k\), для которого \(12^k\mid100!\).
Разложите \(12=2^2\cdot3\).
Нужно \(2k\le v_2(100!)=97\) и \(k\le v_3(100!)=48\). Поэтому \(k\le48\) в обоих случаях, и ответ \(48\).
Найдите \(v_3\left(\binom{30}{10}\right)\).
Используйте \(\binom{30}{10}=30!/(10!20!)\).
\(v_3(30!)=10+3+1=14\), \(v_3(10!)=3+1=4\), \(v_3(20!)=6+2=8\). Поэтому \(v_3\left(\binom{30}{10}\right)=14-4-8=2\).
Докажите, что \(v_p(ab)=v_p(a)+v_p(b)\) для простого \(p\).
Запишите \(a=p^r u\), \(b=p^s v\), где \(p\nmid u,v\).
Пусть \(a=p^r u\), \(b=p^s v\), где \(p\nmid u\) и \(p\nmid v\). Тогда \(ab=p^{r+s}uv\), причём \(p\nmid uv\). Значит, показатель \(p\) в \(ab\) равен \(r+s\), то есть \(v_p(a)+v_p(b)\).
Сколько нулей в конце \(100!\) в системе счисления с основанием \(12\)?
Нужно найти наибольшее \(k\), для которого \(12^k\mid100!\).
Так как \(12=2^2\cdot3\), число нулей равно \(\min(\lfloor v_2(100!)/2\rfloor, v_3(100!))=\min(48,48)=48\).
Докажите, что \(2^n\nmid n!\) для любого натурального \(n\).
Оцените \(v_2(n!)\) сверху геометрической суммой.
По формуле Лежандра \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots\). Каждое слагаемое не превосходит соответствующего \(n/2^i\), а хотя бы первое строго меньше или вся сумма floors строго меньше \(n/2+n/4+\cdots=n\). Значит, \(v_2(n!)
Найдите наибольшее \(k\), для которого \(30^k\mid200!\).
Разложите \(30=2\cdot3\cdot5\).
\(v_2(200!)=197\), \(v_3(200!)=66+22+7+2=97\), \(v_5(200!)=40+8+1=49\). Так как \(30^k\) требует по \(k\) каждого простого \(2,3,5\), ответ равен \(\min(197,97,49)=49\).
Найдите \(v_5\left(\binom{100}{25}\right)\).
Вычтите показатели в \(100!\), \(25!\) и \(75!\).
\(v_5(100!)=20+4=24\), \(v_5(25!)=5+1=6\), \(v_5(75!)=15+3=18\). Разность \(24-6-18=0\). Значит, \(\binom{100}{25}\) не делится на \(5\).
Найдите наибольшее \(k\), для которого \(2^k\mid\prod_{i=1}^{100} i(i+1)\).
Заметьте, что произведение равно \(100!\cdot101!\).
\(\prod_{i=1}^{100} i(i+1)=(1\cdot2\cdots100)(2\cdot3\cdots101)=100!\cdot101!\). Поэтому показатель двойки равен \(v_2(100!)+v_2(101!)=97+97=194\). Ответ: \(194\).
Найдите \(v_2\left(\frac{100!}{50!}\right)\).
Вычтите \(v_2(50!)\) из \(v_2(100!)\).
\(v_2(100!)=97\), \(v_2(50!)=25+12+6+3+1=47\). Поэтому искомый показатель равен \(97-47=50\).
Докажите, что \(\binom{2n}{n}\) чётно для любого натурального \(n\).
Пусть \(2^t\) - наибольшая степень двойки, делящая \(n\). Посмотрите на слагаемое формулы Лежандра с \(2^{t+1}\).
Нужно доказать, что \(v_2((2n)!)-2v_2(n!)>0\). Пусть \(n=2^t u\), где \(u\) нечётно. В сумме Лежандра рассмотрим слагаемое \(2^{t+1}\): \(\lfloor2n/2^{t+1}\rfloor-2\lfloor n/2^{t+1}\rfloor=\lfloor u\rfloor-2\lfloor u/2\rfloor=1\). Остальные слагаемые неотрицательны, значит \(v_2\left(\binom{2n}{n}\right)\ge1\).
Докажите, что произведение любых \(n\) последовательных целых чисел делится на \(n!\).
Докажите неравенство \(v_p(A)\ge v_p(n!)\) для каждого простого \(p\).
Пусть \(A=(m+1)(m+2)\cdots(m+n)\). Среди этих \(n\) чисел не меньше \(\lfloor n/p\rfloor\) кратны \(p\), не меньше \(\lfloor n/p^2\rfloor\) кратны \(p^2\), и так далее. Поэтому \(v_p(A)\ge\lfloor n/p\rfloor+\lfloor n/p^2\rfloor+\cdots=v_p(n!)\). Это верно для каждого простого \(p\), значит \(n!\mid A\).
Найдите все натуральные \(n\), для которых \(2^{n-1}\mid n!\).
Используйте формулу \(v_2(n!)=n-s_2(n)\), где \(s_2(n)\) - сумма цифр \(n\) в двоичной записи.
Из формулы Лежандра следует известное тождество \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots=n-s_2(n)\), где \(s_2(n)\) - сумма цифр в двоичной записи \(n\). Условие \(2^{n-1}\mid n!\) равносильно \(v_2(n!)\ge n-1\), то есть \(n-s_2(n)\ge n-1\). Отсюда \(s_2(n)\le1\). Для натурального \(n\) это возможно только тогда, когда в двоичной записи ровно одна единица, то есть \(n\) является степенью двойки. Проверка обратного направления: если \(n=2^r\), то \(s_2(n)=1\), значит \(v_2(n!)=n-1\), и делимость выполнена.
Найдите наибольшее \(k\), для которого \(36^k\mid150!\).
Разложите \(36=2^2\cdot3^2\).
\(v_2(150!)=75+37+18+9+4+2+1=146\). \(v_3(150!)=50+16+5+1=72\). Для \(36^k=2^{2k}3^{2k}\) нужно \(2k\le146\) и \(2k\le72\), поэтому \(k\le73\) и \(k\le36\). Ответ: \(36\).
Докажите, что \(n!\) не делится на \(3^n\) ни при каком натуральном \(n\).
Оцените \(v_3(n!)\) сверху суммой \(n/3+n/9+\cdots\).
По Лежандру \(v_3(n!)=\lfloor n/3\rfloor+\lfloor n/9\rfloor+\cdots\). Эта сумма строго меньше \(n/3+n/9+\cdots=n/2\), а значит тем более меньше \(n\). Поэтому \(v_3(n!)
Лестницы