Number TheoryDifficulty 45-959 tagged problems

p-adic Valuations

p-adic Valuations is the habit of counting the exponent of a prime inside an integer to sharpen divisibility arguments. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$v_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor \qquad (\text{Legendre's formula})$$

The $p$-adic valuation $v_p(m)$ is the exponent of the prime $p$ in $m$, and Legendre's formula counts exactly how many times $p$ divides a factorial.

Why It Works

1
$v_p$ obeys $v_p(ab) = v_p(a) + v_p(b)$, so $v_p(n!) = \sum_{m=1}^{n} v_p(m)$.
2
Among $1, \dots, n$ there are $\lfloor n/p \rfloor$ multiples of $p$, each contributing at least one factor of $p$.
3
The $\lfloor n/p^2 \rfloor$ multiples of $p^2$ each contribute an extra factor, the $\lfloor n/p^3 \rfloor$ multiples of $p^3$ one more, and so on.
4
Summing these contributions gives $v_p(n!) = \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \cdots$.

Worked Examples

Example 1

How many trailing zeros does $100!$ have?

1
Trailing zeros come from factors of $10 = 2 \cdot 5$; since $5$s are scarcer than $2$s, count $v_5(100!)$.
2
Apply Legendre: $\lfloor 100/5 \rfloor + \lfloor 100/25 \rfloor + \lfloor 100/125 \rfloor = 20 + 4 + 0$.
3
So $v_5(100!) = 24$. We have $v_2(100!) > 24$ for free: term by term $\lfloor 100/2^i \rfloor \ge \lfloor 100/5^i \rfloor$ (multiples of $2^i$ are at least as common as multiples of $5^i$), so $v_2(n!) \ge v_5(n!)$ always. Hence the number of $10$s is $\min(v_2, v_5) = v_5(100!) = 24$.
4
Each factor of $10$ gives one trailing zero.

Answer:

$24$

Warm-up

Find $v_2(50!)$, the exponent of $2$ in $50!$.

1
Apply Legendre's formula with $p = 2$, $n = 50$: $v_2(50!) = \sum_{i \ge 1} \lfloor 50/2^i \rfloor$.
2
Compute the terms: $\lfloor 50/2 \rfloor = 25$, $\lfloor 50/4 \rfloor = 12$, $\lfloor 50/8 \rfloor = 6$, $\lfloor 50/16 \rfloor = 3$, $\lfloor 50/32 \rfloor = 1$, and $\lfloor 50/64 \rfloor = 0$.
3
Sum: $25 + 12 + 6 + 3 + 1 = 47$.
4
So $2^{47} \mid 50!$ but $2^{48} \nmid 50!$.

Answer:

$47$

Contest level

Find the largest integer $n$ such that $3^n$ divides $100!$.

1
This asks for $v_3(100!)$. Apply Legendre with $p = 3$: $v_3(100!) = \sum_{i \ge 1} \lfloor 100/3^i \rfloor$.
2
Compute: $\lfloor 100/3 \rfloor = 33$, $\lfloor 100/9 \rfloor = 11$, $\lfloor 100/27 \rfloor = 3$, $\lfloor 100/81 \rfloor = 1$, $\lfloor 100/243 \rfloor = 0$.
3
Sum: $33 + 11 + 3 + 1 = 48$.
4
There is a slick check via the digit-sum form $v_p(n!) = \frac{n - s_p(n)}{p-1}$: in base $3$, $100 = 10201_3$ with digit sum $s_3(100) = 1+0+2+0+1 = 4$, so $v_3(100!) = \frac{100 - 4}{3 - 1} = \frac{96}{2} = 48$. ✓

Answer:

$48$

Olympiad / Challenge

Prove that the central binomial coefficient $\binom{2n}{n}$ is even for every positive integer $n$.

1
We compute $v_2\!\left(\binom{2n}{n}\right)$ and show it is at least $1$. Use Legendre on $\binom{2n}{n} = \frac{(2n)!}{n!\,n!}$: $v_2 = \sum_{i \ge 1}\left(\lfloor 2n/2^i \rfloor - 2\lfloor n/2^i \rfloor\right)$.
2
By Kummer's theorem this sum equals the number of carries when adding $n + n$ in base $2$. Equivalently, in terms of binary digit sums, $v_2\!\left(\binom{2n}{n}\right) = 2 s_2(n) - s_2(2n)$.
3
Doubling shifts the binary representation one place left and appends a $0$, so $s_2(2n) = s_2(n)$. Hence $v_2\!\left(\binom{2n}{n}\right) = 2 s_2(n) - s_2(n) = s_2(n)$.
4
For $n \ge 1$ the digit sum $s_2(n) \ge 1$, so $v_2\!\left(\binom{2n}{n}\right) = s_2(n) \ge 1$, meaning $2 \mid \binom{2n}{n}$. (It also shows $\binom{2n}{n}$ is a power of $2$ times an odd number with exactly $s_2(n)$ factors of $2$.)

Answer:

$v_2\!\left(\binom{2n}{n}\right) = s_2(n) \ge 1$, so $\binom{2n}{n}$ is always even.

Going Deeper

Generalization: Legendre's formula has the compact digit-sum form $v_p(n!) = \frac{n - s_p(n)}{p - 1}$, where $s_p(n)$ is the sum of the base-$p$ digits of $n$. For binomial coefficients, Kummer's theorem upgrades this: $v_p\!\left(\binom{m+n}{m}\right)$ equals the number of carries when adding $m + n$ in base $p$.
Where it appears: counting trailing zeros of $n!$ (count $v_5$), proving binomial coefficients are integers, locating the exact power of a prime in factorials/binomials/multinomials, and as the engine inside Lifting the Exponent and many divisibility proofs.
Pitfall: the sum is finite — stop once $p^i > n$ (all later terms are $0$); a common slip is to keep adding or to miscount $\lfloor n/p^i \rfloor$. Also note trailing zeros of $n!$ are governed by $\min(v_2, v_5) = v_5$ because fives are always scarcer than twos — do NOT add $v_2$ and $v_5$.

Spot the Signal

Look for problems where the key step is counting the exponent of a prime inside an integer to sharpen divisibility arguments.
You can describe the hard part as counting the exponent of a prime inside an integer to sharpen divisibility arguments, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for p-adic valuations, then rewrite the givens around it.
Name the relation that makes p-adic Valuations legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use p-adic Valuations just because the surface looks familiar; verify the required condition first.
Applying p-adic Valuations because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let p-adic valuations reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is counting the exponent of a prime inside an integer to sharpen divisibility arguments.