
Kummer's theorem
The power of a prime in a binomial coefficient is the number of carries when the two parts are added in that prime's base, so a question about divisibility becomes a question about digits.
Every entry of Pascal's triangle is a binomial coefficient C(n, k), the number of ways to choose k things from n. Fix a prime p and write v_p(m) for the power of p in m, so v_3(18) = 2 and v_5(18) = 0. Kummer's theorem (Kummer 1852, Wikipedia) says that v_p(C(n, k)) is the number of carries when k and n - k are added in base p. The two parts add up to n, so it is the addition that lands on n that is watched.
A carry is the one from school. Add column by column from the right; when a column reaches p or more, write its excess over p and carry 1 into the next column. In base ten, 7 + 5 writes 2 and carries 1. In base three the digits 2 and 1 add to 3, which is written 10: the column writes 0 and carries 1.
The first case is C(6, 2) = 15 = 3 x 5, with 6 = 2 + 4. In base 2 the parts are 10 and 100; no column holds two 1s, there is no carry, and 15 is odd. In base 3 they are 2 and 11: the units column gives 2 + 1 = 3 and carries, the next gives 0 + 1 + 1 = 2 and does not, so there is one carry and 3 divides 15 once. In base 5 the parts 2 and 4 give 6, which carries, so 5 divides 15 once. In base 7, 2 + 4 = 6 does not carry, and 7 does not divide 15. Prime by prime that is the factorisation 3 x 5. A prime larger than n never carries, because both parts are below it.
A case with two carries is C(10, 5) = 252 = 2^2 x 3^2 x 7, with 10 = 5 + 5. In base 2, 101 + 101 carries in the units column and again in the top column. In base 3, 12 + 12 carries in the units column (2 + 2 = 4) and again in the next (1 + 1 + 1 = 3). In base 5, 10 + 10 = 20 does not carry. In base 7, 5 + 5 = 10 carries once. The powers are 2, 2, 0 and 1 at p = 2, 3, 5, 7, and 4 x 9 x 7 = 252 confirms them.
The figure is Pascal's triangle down to row 26, row 0 at the top and 378 cells in all. A cell is inked when 3 does not divide C(n, k), which by the theorem is when k and n - k add in base 3 without a carry; the other cells are faint dots. The 216 inked cells draw the same self-copying shape as the odd entries of the triangle, built from threes instead of twos: the 27 rows are six copies of the 9 rows round three empty gaps, and each copy is six copies of the 3 rows. A pair adds without a carry exactly when every base-3 digit of k is at most the digit of n in its place, since k and n - k then split each digit of n between them. So row n holds one choice of k_i from 0 to n_i per digit, (n_0 + 1)(n_1 + 1)... cells in all. Row 26 is 222 in base 3 and holds 3 x 3 x 3 = 27, every cell, so no entry of row 26 is divisible by 3. Row 10 is 101 and holds 2 x 1 x 2 = 4: of 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1 only the two 1s and the two 10s are not divisible by 3.
The middle entries C(2k, k) are the easiest family, because k is added to itself and each column doubles a digit. Take an odd prime p. Then p does not divide C(2k, k) exactly when every digit of k is at most (p - 1)/2. If every digit is, each column holds 2d <= p - 1 and nothing carries into it, so it does not carry out, from the units column up. If some digit is bigger, take the lowest one: nothing has carried into it, and 2d >= p + 1 carries. At p = 3 the allowed digits are 0 and 1, so k = 3 (10) and k = 4 (11) pass, with C(6, 3) = 20 and C(8, 4) = 70 not divisible by 3, while k = 2 and k = 5 (12) fail, with C(4, 2) = 6 and C(10, 5) = 252, the second having the two carries found above. Below p^L there are ((p + 1)/2)^L such k, (p + 1)/2 digits to pick from in each place: 8 below 27, namely 0, 1, 3, 4, 9, 10, 12 and 13.
The next family C(3k, k) adds k to 2k, and now the two rows differ. The digit of 2k in a column is not the double of the digit of k: it is 2d plus the carry the doubling sent in from the column below, less p if that overflows. So whether a column of k + 2k carries depends on its own digit and on one more bit, the carry of the doubling below it. At p = 7 take the digits 2 and 4. The digit 2 alone, in k = 14 = 20 in base 7, is fine: 2k = 28 = 40 and 2 + 4 = 6 does not carry. The digit 4 alone, k = 4, is fine: 2k = 8 = 11 and 4 + 1 = 5, then 0 + 1 = 1, no carry. But k = 18 = 24 has 2k = 36 = 51, because doubling the 4 carried a 1 up, and the column of the 2 reads 2 + 5 = 7, a carry: 7 divides C(54, 18) once, and divides neither C(42, 14) nor C(12, 4). No list of allowed digits can say that 2 and 4 are each allowed and 24 is not. The rule has to remember a carry, so it is a small machine with two states, one for the doubling having carried and one for it not having, reading the digits of k from the units up.
The proof starts from counting the powers of p in a factorial. Legendre's formula (Wikipedia) says v_p(n!) = floor(n/p) + floor(n/p^2) + floor(n/p^3) + ...: the first term counts the multiples of p up to n, the second counts the multiples of p^2 once more, and so on, so a number holding p^e is counted e times. In digits it reads v_p(n!) = (n - s_p(n))/(p - 1), where s_p(n) is the digit sum of n in base p. To see it, put n = sum_j d_j p^j. Then floor(n/p^i) = sum_(j >= i) d_j p^(j-i), and adding over i gives sum_j d_j (p^(j-1) + ... + 1) = sum_j d_j (p^j - 1)/(p - 1). For 6! = 720 = 2^4 x 3^2 x 5: at p = 2, 6 = 110 has s_2(6) = 2 and (6 - 2)/1 = 4; at p = 3, 6 = 20 has s_3(6) = 2 and (6 - 2)/2 = 2.
Now C(n, k) = n!/(k! (n - k)!), so v_p(C(n, k)) = v_p(n!) - v_p(k!) - v_p((n - k)!), and the formula turns this into (s_p(k) + s_p(n - k) - s_p(n))/(p - 1), the three copies of n, k and n - k cancelling. It remains to see that this is the number of carries. Add k and n - k with digits a_i and b_i, let c_i be the carry into column i with c_0 = 0, and let n_i be the digit written, so n_i = a_i + b_i + c_i - p c_(i+1). Add over all the columns of n: s_p(n) = s_p(k) + s_p(n - k) + sum c_i - p sum c_(i+1). Both carry sums are the total number of carries C, so s_p(n) = s_p(k) + s_p(n - k) - (p - 1) C, and C = (s_p(k) + s_p(n - k) - s_p(n))/(p - 1) = v_p(C(n, k)). In words: a carry takes p out of one column and puts 1 into the next, so it costs the digit sum exactly p - 1. Check C(6, 2) at p = 3: s_3(2) = 2, s_3(4) = 2 (11), s_3(6) = 2 (20), and (2 + 2 - 2)/2 = 1, the one carry found above.
In the tree
Mobius and primes on the Kummer sets works with the integers k for which p does not divide C(3k, k), read by the carry states above, and asks how the Mobius function and the primes behave on them. The Mobius meter does the same on the digits 0 to (p - 1)/2 that C(2k, k) allows, under the name of the half interval. The Kummer sets demo draws the integers k with p not dividing C(ak, bk) level by level, each cell inked by the carry state its digits end in.