Practice
Find \(v_2(72)\).
Factor \(72\) into primes.
\(72=2^3\cdot3^2\), hence \(v_2(72)=3\).
Find \(v_5(1000)\).
Use \(1000=10^3\).
\(1000=2^3\cdot5^3\). Therefore \(v_5(1000)=3\).
Find \(v_3(50!)\).
Add \(\lfloor50/3\rfloor+\lfloor50/9\rfloor+\lfloor50/27\rfloor\).
By Legendre's formula, \(v_3(50!)=16+5+1=22\).
How many trailing zeros does \(80!\) have in decimal notation?
Count fives.
The number of zeros is \(v_5(80!)=\lfloor80/5\rfloor+\lfloor80/25\rfloor=16+3=19\).
Find the largest \(k\) such that \(2^k\mid100!\).
This is \(v_2(100!)\).
\(v_2(100!)=50+25+12+6+3+1=97\). Thus the largest \(k\) is \(97\).
Find \(v_2(2026!)\).
Add the integer parts after division by \(2,4,8,\ldots\).
\(v_2(2026!)=1013+506+253+126+63+31+15+7+3+1=2018\).
Find the largest \(k\) such that \(12^k\mid100!\).
Factor \(12=2^2\cdot3\).
We need \(2k\le v_2(100!)=97\) and \(k\le v_3(100!)=48\). Hence \(k\le48\) in both cases, and the answer is \(48\).
Find \(v_3\left(\binom{30}{10}\right)\).
Use \(\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\). Therefore \(v_3\left(\binom{30}{10}\right)=14-4-8=2\).
Prove that \(v_p(ab)=v_p(a)+v_p(b)\) for prime \(p\).
Write \(a=p^r u\), \(b=p^s v\), where \(p\nmid u,v\).
Let \(a=p^r u\), \(b=p^s v\), where \(p\nmid u\) and \(p\nmid v\). Then \(ab=p^{r+s}uv\), and \(p\nmid uv\). Hence the exponent of \(p\) in \(ab\) is \(r+s\), namely \(v_p(a)+v_p(b)\).
How many trailing zeros does \(100!\) have in base \(12\)?
Find the largest \(k\) such that \(12^k\mid100!\).
Since \(12=2^2\cdot3\), the number of zeros is \(\min(\lfloor v_2(100!)/2\rfloor, v_3(100!))=\min(48,48)=48\).
Prove that \(2^n\nmid n!\) for every positive integer \(n\).
Bound \(v_2(n!)\) above by a geometric sum.
By Legendre's formula, \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots\). Each term is at most the corresponding \(n/2^i\), and the sum of floors is strictly less than \(n/2+n/4+\cdots=n\). Thus \(v_2(n!)
Find the largest \(k\) such that \(30^k\mid200!\).
Factor \(30=2\cdot3\cdot5\).
\(v_2(200!)=197\), \(v_3(200!)=66+22+7+2=97\), \(v_5(200!)=40+8+1=49\). Since \(30^k\) requires \(k\) copies of each prime \(2,3,5\), the answer is \(\min(197,97,49)=49\).
Find \(v_5\left(\binom{100}{25}\right)\).
Subtract the exponents in \(100!\), \(25!\), and \(75!\).
\(v_5(100!)=20+4=24\), \(v_5(25!)=5+1=6\), \(v_5(75!)=15+3=18\). The difference is \(24-6-18=0\). Hence \(\binom{100}{25}\) is not divisible by \(5\).
Find the largest \(k\) such that \(2^k\mid\prod_{i=1}^{100} i(i+1)\).
Notice that the product equals \(100!\cdot101!\).
\(\prod_{i=1}^{100} i(i+1)=(1\cdot2\cdots100)(2\cdot3\cdots101)=100!\cdot101!\). Thus the exponent of \(2\) is \(v_2(100!)+v_2(101!)=97+97=194\). Answer: \(194\).
Find \(v_2\left(\frac{100!}{50!}\right)\).
Subtract \(v_2(50!)\) from \(v_2(100!)\).
\(v_2(100!)=97\), \(v_2(50!)=25+12+6+3+1=47\). Therefore the required exponent is \(97-47=50\).
Prove that \(\binom{2n}{n}\) is even for every positive integer \(n\).
Let \(2^t\) be the largest power of two dividing \(n\). Look at the Legendre term with \(2^{t+1}\).
We need to prove \(v_2((2n)!)-2v_2(n!)>0\). Let \(n=2^t u\), where \(u\) is odd. In Legendre's sum, consider the term with \(2^{t+1}\): \(\lfloor2n/2^{t+1}\rfloor-2\lfloor n/2^{t+1}\rfloor=\lfloor u\rfloor-2\lfloor u/2\rfloor=1\). All other terms are nonnegative, so \(v_2\left(\binom{2n}{n}\right)\ge1\).
Prove that the product of any \(n\) consecutive integers is divisible by \(n!\).
Prove \(v_p(A)\ge v_p(n!)\) for every prime \(p\).
Let \(A=(m+1)(m+2)\cdots(m+n)\). Among these \(n\) numbers, at least \(\lfloor n/p\rfloor\) are divisible by \(p\), at least \(\lfloor n/p^2\rfloor\) are divisible by \(p^2\), and so on. Therefore \(v_p(A)\ge\lfloor n/p\rfloor+\lfloor n/p^2\rfloor+\cdots=v_p(n!)\). This holds for every prime \(p\), so \(n!\mid A\).
Find all positive integers \(n\) such that \(2^{n-1}\mid n!\).
Use the formula \(v_2(n!)=n-s_2(n)\), where \(s_2(n)\) is the sum of binary digits of \(n\).
Legendre's formula implies the identity \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots=n-s_2(n)\), where \(s_2(n)\) is the sum of binary digits of \(n\). The condition \(2^{n-1}\mid n!\) is equivalent to \(v_2(n!)\ge n-1\), that is, \(n-s_2(n)\ge n-1\). Hence \(s_2(n)\le1\). For a positive integer \(n\), this means the binary representation has exactly one \(1\), so \(n\) is a power of two. Conversely, if \(n=2^r\), then \(s_2(n)=1\), hence \(v_2(n!)=n-1\), and the divisibility holds.
Find the largest \(k\) such that \(36^k\mid150!\).
Factor \(36=2^2\cdot3^2\).
\(v_2(150!)=75+37+18+9+4+2+1=146\). \(v_3(150!)=50+16+5+1=72\). For \(36^k=2^{2k}3^{2k}\), we need \(2k\le146\) and \(2k\le72\), so \(k\le73\) and \(k\le36\). Answer: \(36\).
Prove that \(n!\) is not divisible by \(3^n\) for any positive integer \(n\).
Bound \(v_3(n!)\) above by \(n/3+n/9+\cdots\).
By Legendre, \(v_3(n!)=\lfloor n/3\rfloor+\lfloor n/9\rfloor+\cdots\). This sum is strictly less than \(n/3+n/9+\cdots=n/2\), hence certainly less than \(n\). Therefore \(v_3(n!)