{"id":541,"date":"2019-06-29T22:21:23","date_gmt":"2019-06-29T22:21:23","guid":{"rendered":"http:\/\/funfacts.104.42.120.246.xip.io\/?page_id=541"},"modified":"2019-12-03T19:53:32","modified_gmt":"2019-12-03T19:53:32","slug":"lucas-theorem","status":"publish","type":"page","link":"https:\/\/math.hmc.edu\/funfacts\/lucas-theorem\/","title":{"rendered":"Lucas’ Theorem"},"content":{"rendered":"\n

Lucas’ Theorem: If p is a prime number, and N has base p representation (aj<\/sub>,…,a1<\/sub>,a0<\/sub>) and k has base p representation (bj<\/sub>,…,b1<\/sub>,b0<\/sub>), then (N CHOOSE k) is congruent [mod p] to
(aj<\/sub> CHOOSE bj<\/sub>)…(a1<\/sub> CHOOSE b1<\/sub>)(a0<\/sub> CHOOSE b0<\/sub>).<\/p>\n\n\n\n

Example: Let N = 588, k = 277, p = 5. 
N = 588 has base 5 representation (4323). 
k = 277 has base 5 representation (2102). 
Thus by Lucas’ Theorem, (588 CHOOSE 277) is congruent [mod 5] to(4 CHOOSE 2) (3 CHOOSE 1) (2 CHOOSE 0) (3 CHOOSE 2)which is 54 = 4 [mod 5].<\/p>\n\n\n\n

Fun Corollary: If p is prime and N has base p representation (aj<\/sub>,…,a1<\/sub>,a0<\/sub>), then there are exactly (1+aj<\/sub>)…(1+a1<\/sub>)(1+a0<\/sub>) values of k for which (N CHOOSE k) is NOT a multiple of p. This is the number of non-multiples of p in the N-th row of\u00a0Pascal’s Triangle.<\/p>\n\n\n\n

Example: Since 588 = (4323) in base 5, then (588 CHOOSE k) is a non-multiple of 5 for exactly 5*4*3*4 = 240 values of k. The 588th row of Pascal’s Triangle will have 589 – 240 = 349 multiples of 5.<\/p>\n\n\n\n

A special case of this is\u00a0Odd Numbers in Pascal’s Triangle.<\/p>\n\n\n\n

The Math Behind the Fact:<\/strong>
The proof of Lucas’ Theorem is based on this observation: for p prime and r > 0, (pr<\/sup> CHOOSE k) is a multiple of p for all 0 < k < pr<\/sup>. To show this, note for 0 < k < N that (N CHOOSE k) = (N\/k)(N-1 CHOOSE k-1). So when N = pr<\/sup>, we havek*(pr<\/sup> CHOOSE k) = pr<\/sup> (pr<\/sup>-1 CHOOSE k-1).At least r powers of p divide the right side of the equation above, whereas at most r-1 powers of p divide k. Thus p must divide (pr<\/sup> CHOOSE k). (Note this argument only works when p is prime.)<\/p>\n\n\n\n

When k = 0 or pr<\/sup>, then (pr<\/sup> CHOOSE k)=1. Otherwise (pr<\/sup> CHOOSE k)=0 [mod p]. Then the binomial theorem shows that when p is prime,(1+x)p^r<\/sup> = 1 + xp^r<\/sup> [mod p].(This is sometimes called the “Freshman Binomial Theorem”.)<\/p>\n\n\n\n

Now we show that (588 CHOOSE 277) is congruent to 54 [mod 5]. The general case is similar. In the polynomial (1+x)588<\/sup>, the coefficient of x277<\/sup> will be (588 CHOOSE 277) [mod 5]. But(1+x)588<\/sup> = (1+x)4(125)<\/sup> (1+x)3(25)<\/sup> (1+x)2(5)<\/sup> (1+x)3<\/sup>and our observation above shows that this is congruent [mod 5] to(1+x125<\/sup>)4<\/sup> (1+x25<\/sup>)3<\/sup> (1+x5<\/sup>)2<\/sup> (1+x)3<\/sup>.Now how can we create an x277<\/sup> term? Only by using exactly two x125<\/sup> terms, one x25<\/sup>, no x5<\/sup> terms, and two x1<\/sup> terms. How many ways can we do that? Exactly (4 CHOOSE 2)(3 CHOOSE 1)(2 CHOOSE 0)(3 CHOOSE 2) ways, as predicted!<\/p>\n\n\n\n

How to Cite this Page:<\/strong> 
Su, Francis E., et al. “Lucas’ Theorem.” Math Fun Facts<\/em>. <http:\/\/www.math.hmc.edu\/funfacts>.<\/p>\n\n\n\n

References:<\/strong>
R. P. Stanley, Enumerative Combinatorics<\/a><\/em>, Wadsworth & Brooks\/Cole, 1986.<\/p>\n\n\n\n

Fun Fact suggested by: <\/strong>
Arthur Benjamin <\/p>\n","protected":false},"excerpt":{"rendered":"

Lucas’ Theorem: If p is a prime number, and N has base p representation (aj,…,a1,a0) and k has base p...<\/p>\n","protected":false},"author":7,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"tags":[57,9,10,15,49],"class_list":["post-541","page","type-page","status-publish","hentry","tag-advanced","tag-combinatorics","tag-numtheory","tag-polynomial","tag-prime"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/541","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/comments?post=541"}],"version-history":[{"count":3,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/541\/revisions"}],"predecessor-version":[{"id":1512,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/541\/revisions\/1512"}],"wp:attachment":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/media?parent=541"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/tags?post=541"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}