Lucas' theorem

From Groupprops
Jump to: navigation, search


Suppose and are nonnegative integers and is a prime number. Suppose and are the expressions of and in base , so that each is in the set . if , define for . Then, we have:

By convention, if or if .

In particular, we have the following: If is a power of and , then is relatively prime to . For more on this special case and alternative proofs of it, see Lucas' theorem prime power case.