Chapter
Theory
\(v_p(n)\) is the exponent of the prime \(p\) in the factorisation of \(n\). Instead of asking whether a number is divisible, we ask how many times it is divisible by \(p\). This turns problems about prime powers, factorials, and binomial coefficients into exact computations.
If \(p\) is prime, then \(v_p(ab)=v_p(a)+v_p(b)\), and \(v_p(a^k)=k v_p(a)\). For factorials we use Legendre's formula: \(v_p(n!)=\lfloor n/p \rfloor+\lfloor n/p^2 \rfloor+\lfloor n/p^3 \rfloor+\cdots\). The number of trailing zeros of \(n!\) in decimal notation is \(v_5(n!)\), because there are more factors \(2\) than factors \(5\).
Use valuations when the problem asks for the largest \(k\) such that \(p^k\mid N\), or when factorials, products of consecutive integers, binomial coefficients, trailing zeros, or divisibility by a composite number \(2^a3^b5^c\) appear.
Phrases such as largest power, number of zeros, divisible by \(m^k\), or find the exponent of a prime almost always point to \(v_p\). If the number is composite, factor it into primes and take the minimum of the resulting restrictions.
Do not count only multiples of \(p\): multiples of \(p^2\) contribute extra. For decimal zeros, the limiting factor is the number of fives, not twos. For \(m^k\mid N\), where \(m\) is composite, every prime divisor of \(m\) must be considered.
1. Which prime \(p\) matters? 2. Should the modulus be factored? 3. For a factorial, has Legendre's formula included all powers of \(p\)? 4. For a composite base, has the minimum been taken? 5. Is the found exponent truly maximal?
Examples
This teaches reading a factorisation.
Problem. Find \(v_2(72)\) and \(v_3(72)\).
We have \(72=2^3\cdot3^2\). Therefore \(v_2(72)=3\), and \(v_3(72)=2\).
Comment. This is not the number of divisors, but the exponent of a specific prime.
This shows how to count the exponent of a prime in a factorial.
Problem. Find \(v_3(100!)\).
By Legendre's formula, \(v_3(100!)=\lfloor100/3\rfloor+\lfloor100/9\rfloor+\lfloor100/27\rfloor+\lfloor100/81\rfloor=33+11+3+1=48\).
Comment. Multiples of \(9\) and \(27\) contribute extra factors of \(3\).
This connects valuations with decimal notation.
Problem. How many zeros are at the end of \(100!\)?
The number of zeros equals the number of factors \(10=2\cdot5\). There are more twos than fives in a factorial, so count fives: \(v_5(100!)=20+4=24\). Answer: \(24\).
Comment. For decimal notation, fives are almost always the limiting factor.
This teaches taking the minimum over prime divisors.
Problem. Find the largest \(k\) such that \(12^k\mid100!\).
Since \(12=2^2\cdot3\), we need \(2k\le v_2(100!)\) and \(k\le v_3(100!)\). Now \(v_2(100!)=50+25+12+6+3+1=97\), and \(v_3(100!)=48\). Hence \(k\le48\) from twos and \(k\le48\) from threes. Answer: \(48\).
Comment. Always factor a composite base.
This shows valuation for a quotient of factorials.
Problem. Find \(v_2\left(\binom{16}{6}\right)\).
Use \(\binom{16}{6}=16!/(6!10!)\). Then \(v_2(16!)=8+4+2+1=15\), \(v_2(6!)=3+1=4\), \(v_2(10!)=5+2+1=8\). Thus \(v_2\left(\binom{16}{6}\right)=15-4-8=3\).
Comment. For binomial coefficients, exponents are subtracted.
This shows that the base need not be decimal.
Problem. How many zeros are at the end of \(100!\) in base \(12\)?
The base is \(12=2^2\cdot3\). We need the maximum \(k\) such that \(12^k\mid100!\). From above, \(v_2(100!)=97\), \(v_3(100!)=48\). Hence \(k=\min(\lfloor97/2\rfloor,48)=48\).
Comment. This is the same as \(12^k\mid100!\), but in a different form.
This prepares for proof problems.
Problem. Prove that for every \(n\ge1\), the number \(n!\) is not divisible by \(2^n\).
By Legendre's formula, \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots\). Each term is strictly less than the corresponding term of the geometric sum \(n/2+n/4+\cdots=n\). Therefore \(v_2(n!)
Comment. Estimating the sum of floors is often easier than finding the exact value.
Olympiad idea: prove divisibility through \(v_p\).
Problem. Prove that the product of any \(n\) consecutive integers is divisible by \(n!\).
Let the product be \(A=(m+1)(m+2)\cdots(m+n)\). For every prime \(p\), we prove \(v_p(A)\ge v_p(n!)\). Among \(n\) consecutive integers, 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. Hence \(v_p(A)\ge\sum_i\lfloor n/p^i\rfloor=v_p(n!)\). This holds for every prime \(p\), so \(n!\mid A\).
Comment. This proof is equivalent to the integrality of a binomial coefficient.
Problems
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!)
Ladders