Why count factors instead of multiplying?
A factorial becomes large quickly, but many questions ask only how often one prime occurs in it. For example, the number of trailing zeros of depends on its factors of ten, not on all its digits. Prime valuations replace the large multiplication by a short sum of integer quotients. They also reveal why the divisibility of a binomial coefficient can be read from ordinary addition in a different base.
Definition 1.3.1
(Factorials and prime valuations)
Throughout, denotes a prime and for , with . For a positive integer , is the exponent of in its unique prime factorization; in particular . For an integer , exactly when , and . We apply subtraction to a quotient only when it is already known to be an integer.
Counting multiples at every level
Theorem 1.3.2
(Factorial valuation formula)
For every integer ,
The sum is finite: its terms vanish once .
Proof
(Each factor is counted once per level)
Each multiple of among contributes at least one factor ; there are of them. Each multiple of contributes one additional factor, and so on. A number divisible by but not is counted exactly times. Adding over the factors of proves the formula. Counting only multiples of would miss the extra copies in .
Worked example 1.3.3
(Trailing zeros of a factorial)
The number of trailing decimal zeros in a positive integer is : every terminal zero removes one factor , and after the smaller exponent is exhausted the quotient is not divisible by ten. For ,
Hence ends in exactly zeros. For a general one must take the minimum; has a factor five but no trailing zero.
Worked example 1.3.4
(The largest power of a composite divisor)
To find the largest with , use . The formula gives and . The two requirements are and , so . In general, if , the largest exponent is . The limiting prime need not be the largest prime dividing .
Digits encode the same count
Write the base- expansion of as , where and all but finitely many digits are zero. Put . Substituting the expansion into the factorial formula and exchanging finite sums yields
The first equality counts, for each digit , its contributions at levels . The formula also proves that is divisible by ; it is not an instruction to round a fraction.
For , the binomial coefficient is an integer: it counts the -element subsets of an -element set. Its valuation is therefore
This identity connects a divisibility question to the carries made when adding and in base .
Theorem 1.3.5
(Carries and divisibility)
For a prime and integers , equals the number of carries in the base- addition of and , counting each column that sends a carry to the next column. In particular, divides exactly when at least one carry occurs.
Proof
(Column equations without place values)
Write the two input digits in column as , the output digit as , and the incoming carry as , with . Inductively, if is zero or one, then ; hence the outgoing carry is also zero or one. Since , this holds in every column, and
Include enough leading zero columns that the final carry is zero. Summing the column equations without their place values gives . The digit formula above completes the proof. A chain of carries counts once for each column that sends one, not once for the entire chain.
Proof X-ray
Two different kinds of counting
The factorial formula counts multiples of prime powers in a product. The carry theorem counts column transfers in an addition. Their equality follows from the digit-sum identity; it does not require a correspondence between individual multiples and individual carries.
Worked example 1.3.6
(A carry chain in base two)
Take , . In base two, and . Their sum is : the first, second and third columns each send a carry, so . Indeed . The carry entering the fourth column produces the leading digit but does not itself make a fourth outgoing carry.
Worked example 1.3.7
(No carry means nondivisibility, not primality)
In base three, and add without a carry to . Consequently . This says nothing by itself about divisibility by another prime: and both divide .
Worked example 1.3.8
(A carry that propagates through four columns)
Find the exact power of dividing . The numbers to add are and , whose binary expansions are and . Starting at the units column, the successive column sums are , , , and . Each sends a carry; the fifth column receives the last carry and outputs without sending another. The result is , and the four outgoing carries give
This is an exact exponent, so divides the coefficient but does not. As an independent check, , and is odd. Counting the final leading digit as another carry would overstate the exponent.
From no carries to a digit-by-digit test
The carry theorem gives more than a way to check one coefficient. It can identify every entry in a row that is not divisible by a chosen prime, without first computing those coefficients. Suppose the base- digits of and are
where missing leading digits are filled with zero.
Theorem 1.3.9
(Digit-by-digit criterion)
Let , with digits as above. The following statements are equivalent.
- ;
- adding to in base produces no carries;
- at every digit position.
Proof
(From the carry theorem to digits)
The carry theorem gives the equivalence of the first two statements. For the second to imply the third, examine each column of the carry-free sum. With no incoming or outgoing carry, the output digit is the sum of the two input digits, so it is at least . Conversely, if every , put . These are valid base- digits, and satisfies . In each column , so this particular addition has no carries. Since , it is exactly the addition in the theorem. The argument works with zeros and leading zero columns; it does not require subtracting digits by a borrowing algorithm.
Concept lensAlgebraic
The digit criterion from a polynomial identity
Modulo , , because divides for . Applying this to each digit gives
Since every , each power arises from at most one choice of digits, so , where a factor is zero when . The nonzero factors are not divisible by , which recovers the criterion and also gives the residue of the coefficient.
Worked example 1.3.10
(List the odd entries without computing the row)
Take and . A permitted index can have a only in positions where has a . The choices are therefore
Exactly these eight coefficients in row are odd. For instance, gives , with no carries, and indeed is odd. In contrast uses the zero in the twos position. Adding to sends one carry, so ; in fact . A failed digit test alone guarantees at least one factor of ; to find its exact exponent, count all outgoing carries.
Now count rather than list. At position , the allowed digit has precisely choices, from through . The choices are independent and only finitely many positions are nonzero. Consequently
The product counts the two endpoint coefficients as well. For in base two, its three digits contribute choices, including and . This is a count of indices, not the value or a congruence class of any one coefficient.
Worked example 1.3.11
(A row in base three)
Write . The three digit positions give , and choices, so exactly of the coefficients are not divisible by . For a permitted example, and add without carrying. For , the threes digit exceeds the corresponding digit of . Indeed and sends one carry; the coefficient is divisible by but not by .
Use symmetry to check a list
Since , a list of nondivisible indices must be symmetric under . The digit criterion makes this visible: when there is no carry, the partner has digits , which are also allowed. Thus the row list pairs with , with , with , and with . This is a useful check on a hand-built list, not a second count to add to the product.
When and , the possible fixed index is not on the list. Indeed, the least significant in the binary expansion of is added to another in , so at least one carry occurs and is even. At the single coefficient is an exception to that positive-row observation. Keeping this fixed-point case separate prevents an unjustified division by two when using symmetry.
When every interior entry has a factor of
The counting formula also distinguishes prime powers from other row indices.
Theorem 1.3.12
(Rows whose interior entries are all divisible by )
Let . Then every interior coefficient , with , is divisible by if and only if is a power of (allowing ). The special case has no interior coefficients, so the statement about them is vacuously true.
Proof
(Counting the permitted indices)
To see why, there are two different endpoint indices, and , and their coefficients are both . Thus every interior coefficient is divisible by exactly when the product equals . Each factor is a positive integer, so a product of has one factor and all other factors . Equivalently, exactly one digit of is and every other digit is : this is precisely . This argument also proves the converse; checking only rows whose index is already known to be a prime power would not.
For example, has only the two nondivisible endpoint coefficients. But has four permitted indices: , , , and . The interior coefficients at and are both , which is not divisible by . Thus it is not enough for the row index merely to be divisible by . At there is just one endpoint index, so the preceding two-endpoint count must be replaced by the single coefficient .
Common errors
Counterexample mode
The level-counting formula needs a prime
Claim: for any integer , the exponent of in is . For and the sum is . But , and is not divisible by , so the largest power of dividing is . The sum sees only multiples of ; the single factors of in and and the extra factor in combine into another factor of . The repair is to factor into primes: here .
A quotient of factorials cannot automatically be assigned a nonnegative valuation until its integrality is established.
Common mistake
(Adding and instead of and )
The carry theorem concerns addition of and , not the addition of and . It counts prime factors with multiplicity: two carries prove divisibility by , not merely by .
Common mistake
(Counting the leading digit as another carry)
In the addition sends four carries; the fifth column receives one and outputs the leading without sending another. Counting that leading digit as a fifth carry would claim , but is not an integer.
Summary
To test a single coefficient for divisibility by , compare the digits of with those of ; to obtain the exact exponent, count the carries in . To count all nondivisible coefficients in a row, multiply the numbers of permitted digits. All three methods require a prime base , and the counting formula includes both endpoints.
Practice
Quick check
(Find the largest integer such that divides .)
Compare the requirements for the prime factors of 18.
Solution · Answer
Here , and . Thus and , so the largest value is .
Quick check
(Determine the exact exponent of in , using carries and an independent calculation.)
Add 4 and 8 in base three.
Solution · Answer
In base three, and ; their sum sends carries from the units and threes columns. The exponent is therefore . Independently, , and , giving . Indeed .
Quick check
(Prove that a prime divides every binomial coefficient with .)
Use factorial valuations or carries, and explain why the endpoints are excluded.
Solution · Answer
For , neither nor contains a factor , whereas contains exactly one. Hence . At and the coefficient is , so the strict inequalities are essential.
Quick check
(Find the exact exponent of in , first by carries and then by factorial valuations.)
Add 8 and 12 in base three; distinguish an incoming carry from a new outgoing carry.
Solution · Answer
In base three, and . The units column gives with no carry; the threes column gives and sends one carry; the nines column gives and sends none. Thus , and . Independently, , , and , so the exponent is . The incoming carry in the last column is the carry already counted, not a second outgoing carry.
Quick check
(For any integer and any prime , explain why the carry theorem gives valuation zero for and .)
What happens when a base-p expansion is added to zero?
Solution · Answer
For the addition is ; for it is . In either case every column has a zero digit from one summand and receives no carry from the preceding column, so no carry is ever sent. The theorem gives valuation zero, as it must because . This includes : the single coefficient is , and the addition has no carries.