Math Core

Many AIME questions ask "what is the largest power of $p$ dividing this number?" The number might be $1000!$ , a binomial coefficient like $\binom{2026}{1013}$ , or a difference of powers like $7^{2048} - 1$ . Three tools answer almost all of them: Legendre's formula for factorials, Kummer's theorem for binomial coefficients, and the lifting-the-exponent lemma (LTE) for $a^n \pm b^n$ .

Valuations

Definition

p-adic valuation

For a prime $p$ and a nonzero integer $n$ , $v_p(n)$ is the exponent of $p$ in the prime factorization of $n$ : the largest $k$ with $p^k \mid n$ .

For example, $v_2(48) = 4$ and $v_3(48) = 1$ . Valuations turn multiplication into addition: $v_p(ab) = v_p(a) + v_p(b)$ . For sums there is only an inequality, $v_p(a + b) \ge \min(v_p(a), v_p(b))$ , with equality when $v_p(a) \ne v_p(b)$ .

Legendre's formula

$v_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots = \frac{n - s_p(n)}{p - 1},$

where $s_p(n)$ is the sum of the base- $p$ digits of $n$ .

Why the first form. $v_p(n!) = \sum_{k=1}^{n} v_p(k)$ . A number $k$ with $v_p(k) = j$ should be counted $j$ times. It is: once among the multiples of $p$ , once among the multiples of $p^2$ , and so on up to $p^j$ . There are $\lfloor n / p^i \rfloor$ multiples of $p^i$ up to $n$ .

Why the second form. Write $n = \sum d_i p^i$ . Then $\lfloor n / p^i \rfloor = d_i + d_{i+1}p + \cdots$ . Summing over $i \ge 1$ , digit $d_j$ contributes $d_j(1 + p + \cdots + p^{j-1}) = d_j \dfrac{p^j - 1}{p - 1}$ . Adding up gives $\dfrac{n - s_p(n)}{p-1}$ .

The case $p = 2$ is especially clean: $v_2(n!) = n - s_2(n)$ , where $s_2(n)$ is the number of $1$ s in binary.

Kummer's theorem

$v_p\!\left(\dbinom{m + n}{m}\right)$ equals the number of carries when you add $m$ and $n$ in base $p$ .

Why. By the digit form of Legendre,

$v_p\binom{m+n}{m} = \frac{s_p(m) + s_p(n) - s_p(m+n)}{p - 1}.$

Each carry reduces the digit sum by $p - 1$ (a $p$ in one column becomes a $1$ in the next), so $s_p(m) + s_p(n) - s_p(m+n) = (p-1) \cdot (\text{carries})$ .

A consequence: $\binom{n}{k}$ is not divisible by $p$ for exactly $\prod (d_i + 1)$ values of $k$ , where $d_i$ are the base- $p$ digits of $n$ (those $k$ whose digits are each at most $n$ 's, so there are no carries). This is Lucas's theorem. For $p = 2$ , the number of odd entries in row $n$ of Pascal's triangle is $2^{s_2(n)}$ . Also $v_2\binom{2n}{n} = s_2(n)$ : adding $n + n$ in binary carries once for every $1$ .

Lifting the exponent

Lifting the exponent (LTE)

Let $p$ be an odd prime with $p \mid a - b$ and $p \nmid a, b$ . Then for every $n \ge 1$ ,

$v_p(a^n - b^n) = v_p(a - b) + v_p(n).$

If also $n$ is odd, then $v_p(a^n + b^n) = v_p(a + b) + v_p(n)$ (when $p \mid a + b$ ).

For $p = 2$ , with $a, b$ odd and $n$ even:

$v_2(a^n - b^n) = v_2(a - b) + v_2(a + b) + v_2(n) - 1.$

For $n$ odd, simply $v_2(a^n - b^n) = v_2(a - b)$ .

Proof for odd $p$ . Two steps.

Step 1: if $p \nmid n$ , $v_p(a^n - b^n) = v_p(a - b)$ . Factor $a^n - b^n = (a - b)(a^{n-1} + a^{n-2}b + \cdots + b^{n-1})$ . Since $a \equiv b \pmod p$ , the second factor is $\equiv n a^{n-1} \not\equiv 0 \pmod p$ .

Step 2: $v_p(a^p - b^p) = v_p(a - b) + 1$ . The second factor is $S = \sum_{i=0}^{p-1} a^{p-1-i} b^i$ . Write $b = a + t$ with $p \mid t$ . Then $a^{p-1-i}b^i \equiv a^{p-1} + i a^{p-2} t \pmod{p^2}$ , so

$S \equiv p a^{p-1} + a^{p-2} t \cdot \frac{p(p-1)}{2} \pmod{p^2}.$

The second term is divisible by $p^2$ (since $p \mid t$ and $p$ is odd, so $\frac{p-1}{2}$ is an integer), and the first is divisible by $p$ exactly once. So $v_p(S) = 1$ .

Now write $n = p^k m$ with $p \nmid m$ and apply Step 2 $k$ times and Step 1 once. The $+$ version follows by replacing $b$ with $-b$ .

The $p = 2$ case. For even $n = 2^k m$ with $m$ odd, factor $a^{2^k} - b^{2^k} = (a - b)(a + b)(a^2 + b^2)(a^4 + b^4)\cdots(a^{2^{k-1}} + b^{2^{k-1}})$ . Each $a^{2^j} + b^{2^j}$ with $j \ge 1$ is $\equiv 2 \pmod 4$ , contributing exactly one $2$ . That gives $v_2(a-b) + v_2(a+b) + (k - 1)$ . The odd part $m$ doesn't change the valuation (Step 1 again).

Common mistake

LTE needs $p \mid a - b$ (or $p \mid a + b$ for the plus version) and $p \nmid ab$ . For $p = 2$ , the formula with $v_2(a + b)$ only holds for even $n$ . Check these conditions before applying it: $v_3(2^n - 1)$ isn't $v_3(1) + v_3(n)$ , because $3 \nmid 2 - 1$ .

Worked example: Legendre two ways

Find $v_2(100!)$ .

Floors: $50 + 25 + 12 + 6 + 3 + 1 = 97$ . Digits: $100 = 1100100_2$ has three $1$ s, so $v_2(100!) = 100 - 3 = 97$ .

Worked example: Kummer

Find $v_3\!\left(\dbinom{100}{50}\right)$ .

$50 = 1212_3$ (since $27 + 2 \cdot 9 + 3 + 2 = 50$ ). Add $1212_3 + 1212_3$ : units $2 + 2 = 4 = 1 \cdot 3 + 1$ , carry; threes $1 + 1 + 1 = 3$ , carry; nines $2 + 2 + 1 = 5$ , carry; twenty-sevens $1 + 1 + 1 = 3$ , carry. Four carries, so $v_3 = 4$ (the sum is $10201_3 = 100$ ).

Worked example: LTE, odd prime

Find the largest $k$ such that $3^k \mid 4^{81} - 1$ .

$3 \mid 4 - 1$ and $3 \nmid 4$ , so $v_3(4^{81} - 1) = v_3(3) + v_3(81) = 1 + 4 = 5$ .

Worked example: LTE, p = 2

Find $v_2(7^{64} - 1)$ .

$64$ is even: $v_2(7 - 1) + v_2(7 + 1) + v_2(64) - 1 = 1 + 3 + 6 - 1 = 9$ .