In number theory

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

, the Lucas' theorem expresses the remainder

Remainder

In arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient....

 of division of the binomial coefficient

Binomial coefficient

In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk , and it is the coefficient of the x k term in...

  by a prime number

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

 p in terms of the base

Radix

In mathematical numeral systems, the base or radix for the simplest case is the number of unique digits, including zero, that a positional numeral system uses to represent numbers. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.In any numeral...

 p expansions of the integers m and n.

Lucas' theorem first appeared in 1878 in papers by Édouard Lucas

Edouard Lucas

François Édouard Anatole Lucas was a French mathematician. Lucas is known for his study of the Fibonacci sequence. The related Lucas sequences and Lucas numbers are named after him.-Biography:...

.

Formulation

For non-negative integers m and n and a prime p, the following congruence relation

Congruence relation

In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure...

 holds:
where
and
are the base p expansions of m and n respectively.

Consequence

• A binomial coefficient is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding digit of m.

Proof

There are several ways to prove Lucas' theorem; here is a combinatorial argument. Let M be a set with m elements, and divide it into m_i cycles of length pⁱ for the various values of i. Then each of these cycles can be rotated separately, so that a group G which is the Cartesian product of cyclic groups C_pⁱ acts on M. It thus also acts on subsets N of size n. Since the number of elements in G is a power of p, the same is true of any of its orbits. Thus in order to compute modulo p, we only need to consider fixed points of this group action. The fixed points are those subsets N that are a union of some of the cycles. More precisely one can show by induction on k-i, that N must have exactly n_i cycles of size pⁱ. Thus the number of choices for N is exactly

Variations and generalizations

• The valuation
  P-adic order
  In number theory, for a given prime number p, the p-adic order or additive p-adic valuation of a number n is the highest exponent ν such that pν divides n. It is commonly abbreviated νp. The most important application of the p-adic order is in constructing the field of p-adic numbers...
  
   of the binomial coefficient w.r.t. a prime p equals the number of carries that occur in addition of n and (m-n) in the base p.
• There exists a generalization of Lucas' theorem to the case of p being a power of prime.