Lucas's theorem

Apr 20, 2026 - 18:52
0 0
Lucas's theorem

Non-prime moduli

← Previous revision Revision as of 13:21, 20 April 2026
Line 60: Line 60:
Lucas's theorem can be generalized to give an expression for the remainder when \tbinom mn is divided by a [[prime power]] ''p''''k''. However, the formulas become more complicated.
Lucas's theorem can be generalized to give an expression for the remainder when \tbinom mn is divided by a [[prime power]] ''p''''k''. However, the formulas become more complicated.


If the modulo is the square of a prime ''p'', the following congruence relation holds for all 0 ≤ ''s'' ≤ ''r'' ≤ ''p'' − 1, ''a'' ≥ 0, and ''b'' ≥ 0:
If the modulus is the square of a prime ''p'', the following congruence relation holds for all 0 ≤ ''s'' ≤ ''r'' ≤ ''p'' − 1, ''a'' ≥ 0, and ''b'' ≥ 0:
:\binom{pa+r}{pb+s}\equiv\binom ab\binom rs(1+pa(H_r-H_{r-s})+pb(H_{r-s}-H_s))\pmod{p^2},
:\binom{pa+r}{pb+s}\equiv\binom ab\binom rs(1+pa(H_r-H_{r-s})+pb(H_{r-s}-H_s))\pmod{p^2},
where H_n=1+\tfrac12+\tfrac13+\cdots+\tfrac1n is the ''n''th [[harmonic number]].{{cite journal |last=Rowland |first=Eric |title=Lucas' theorem modulo ''p''2 |doi=10.1080/00029890.2022.2038004 |journal=American Mathematical Monthly |volume=129 |year=2022 |issue=9 |pages=846–855 |arxiv=2006.11701v3}} Generalizations of Lucas's theorem for higher prime powers ''p''''k'' are also given by Davis and Webb (1990){{cite journal |author=Kenneth S. Davis, William A. Webb |title=Lucas' Theorem for Prime Powers |journal=European Journal of Combinatorics |volume=11 |issue=3 |year=1990 |pages=229–233 |doi=10.1016/S0195-6698(13)80122-9|doi-access= }} and Granville (1997).{{cite journal |author=[[Andrew Granville]] |title=Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers |journal=Canadian Mathematical Society Conference Proceedings |volume=20 |pages=253–275 |year=1997 |url=http://www.dms.umontreal.ca/%7Eandrew/PDF/BinCoeff.pdf |mr=1483922 |url-status=dead |archiveurl=https://web.archive.org/web/20170202003812/http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf |archivedate=2017-02-02 }}
where H_n=1+\tfrac12+\tfrac13+\cdots+\tfrac1n is the ''n''th [[harmonic number]].{{cite journal |last=Rowland |first=Eric |title=Lucas' theorem modulo ''p''2 |doi=10.1080/00029890.2022.2038004 |journal=American Mathematical Monthly |volume=129 |year=2022 |issue=9 |pages=846–855 |arxiv=2006.11701v3}} Generalizations of Lucas's theorem for higher prime powers ''p''''k'' are also given by Davis and Webb (1990){{cite journal |author=Kenneth S. Davis, William A. Webb |title=Lucas' Theorem for Prime Powers |journal=European Journal of Combinatorics |volume=11 |issue=3 |year=1990 |pages=229–233 |doi=10.1016/S0195-6698(13)80122-9|doi-access= }} and Granville (1997).{{cite journal |author=[[Andrew Granville]] |title=Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers |journal=Canadian Mathematical Society Conference Proceedings |volume=20 |pages=253–275 |year=1997 |url=http://www.dms.umontreal.ca/%7Eandrew/PDF/BinCoeff.pdf |mr=1483922 |url-status=dead |archiveurl=https://web.archive.org/web/20170202003812/http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf |archivedate=2017-02-02 }}
Read More