Lucas' theorem is a result about binomial coefficients modulo a prime . It answers questions like:
Lucas' theorem states that for non-negative integers and , and a prime , where and are the base expansions of and respectively. This uses the convention that =0 when .
In particular, is divisible by if and only if at least one of the base- digits of is greater than the corresponding base- digit of .
To look at a tangible example, take Then is even if and only if at least one of the binary digits of is greater than the corresponding binary digits of So, is even because has a greater digit than (specifically, the rightmost digit).
Another interesting consequence is that is always odd, since is all 1s when written in binary; e.g., is always odd.
Find the remainder when is divided by 13.
We first write both 1000 and 300 in terms of the sum of powers of 13: Then apply Lucas' theorem: implying the remainder is 10.
Note: Looking deeper, it is possible to further explore these coefficients throughout Pascal's triangle.
The oranges are stacked as a triangular-based pyramid such that there is one orange on the top, 2 more oranges on the second layer, yet 3 more oranges on the third, and so on until there are 200 pyramidal layers of oranges.
If this big lot is distributed into boxes of 7 oranges each, how many oranges will remain undistributed?
Find a formula for the number of entries in the row of Pascal's triangle that are not divisible by , in terms of the base- expansion of .
Write , . Then is not divisible by if and only if for . There are choices for each (it can be ). So the answer is
Note that in particular if , then all the are equal to , so the product is ; that is, all of the entries in the row are not divisible by .
In fact, for the previous example, taking gives the following result:
Picture for : If we draw a picture of the odd entries in the row of Pascal's triangle (), we get an image that looks very much like the Sierpinski gasket:
This fractality comes from the fact that if , then by Lucas' theorem, so the top rows are reproduced twice side-by-side in the next rows.
What about the middle section? This consists of elements of the form where . In this case, since , at least one of the binary digits of will be greater than the corresponding binary digit of , so that part of the product in Lucas' theorem will be , so all of the entries in the middle section will be even.
Show that .
Let be the expansion of in base . Then Lucas' theorem says and , so both sides are equal.
These are the first few rows of Pascal's triangle:
Each number is derived by adding up the two numbers just above it (and to the left and right) in the previous row. (The numbers on the ends remain 1).
Of the first 1000 rows, as labeled above, how many of them contain all odd numbers?
Image credit: http://www.daviddarling.info/
There are several proofs, but the most down-to-earth one proceeds by induction. The idea is to write by the division algorithm, and then to prove that where . The result will follow by induction since are smaller than , respectively, and the base- expansions of and are just the base- expansions of and with the respective rightmost digits omitted.
To see that the formula above is true, write the left side as and separate out the first terms on top and bottom. These are The denominator is not divisible by , so this is just .
Now the remaining terms come in consecutive groups of ; in each group of there is one term on top and on bottom that is divisible by , and the rest are products of every nonzero element mod , i.e. mod . The on top and on bottom will cancel mod , and we can take the factors out of each of the terms divisible by . What is left is So we get but in the second case, this also equals because both are . So the theorem is true by induction.