TOPICS
Search

Lucas Correspondence Theorem


Let p be prime and

r=r_mp^m+...+r_1p+r_0    (0<=r_i<p)
(1)
k=k_mp^m+...+k_1p+k_0    (0<=k_i<p),
(2)

then

 (r; k)=product_(i=0)^m(r_i; k_i) (mod p).
(3)

This is proved in Fine (1947).

This theorem is the underlying reason that the binomial coefficient (n; k) mod 2 can be computed using bitwise operations AND(NOT(n),k), giving the Sierpiński sieve.


See also

Lucas Correspondence, Sierpiński Sieve

Explore with Wolfram|Alpha

References

Fine, N. J. "Binomial Coefficients Modulo a Prime." Amer. Math. Monthly 54, 589-592, 1947.

Referenced on Wolfram|Alpha

Lucas Correspondence Theorem

Cite this as:

Weisstein, Eric W. "Lucas Correspondence Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LucasCorrespondenceTheorem.html

Subject classifications