Let be prime and
(1)
| |||
(2)
|
then
(3)
|
This is proved in Fine (1947).
This theorem is the underlying reason that the binomial coefficient mod 2 can be computed using bitwise operations AND(NOT(),), giving the Sierpiński sieve.
Let be prime and
(1)
| |||
(2)
|
then
(3)
|
This is proved in Fine (1947).
This theorem is the underlying reason that the binomial coefficient mod 2 can be computed using bitwise operations AND(NOT(),), giving the Sierpiński sieve.
Weisstein, Eric W. "Lucas Correspondence Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LucasCorrespondenceTheorem.html