Практика
Найдите \(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!)