Lucas' theorem

In number theory, the Lucas's theorem states the following:

Let "m" and "n" be non-negative integers, "p" a prime, and: $m=m_kp^k+m_{k-1}p^{k-1}+cdots +m_1p+m_0,$ and: $n=n_kp^k+n_{k-1}p^{k-1}+cdots +n_1p+n_0$ be the base "p" expansions of "m" and "n" respectively. Then: $inom{m}{n}equivprod_{i=0}^kinom{m_i}{n_i}pmod p,$ where $inom{m}{n}=frac{m!}{n!(m-n)!}$ denotes the binomial coefficient of "m" and "n", also known as "m choose n".

In particular, a binomial coefficient $inom{m}{n}$ is divisible by a prime "p" as soon as at least one of the base "p" digits of "n" is greater than the corresponding digit of "m".

References

External links

* [http://planetmath.org/encyclopedia/LucassTheorem.html Lucas's Theorem @ PlanetMath]
*Andrew Granville. [http://www.cecm.sfu.ca/organics/papers/granville/index.html The Arithmetic Properties of Binomial Coefficients] .

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

Gauss-Lucas theorem — In complex analysis, the Gauss Lucas theorem gives a geometrical relation between the roots of a polynomial P and the roots of its derivative P . The set of roots of a real or complex polynomial is a set of points in the complex plane. The… … Wikipedia
Lucas–Lehmer test for Mersenne numbers — This article is about the Lucas–Lehmer test (LLT), that only applies to Mersenne numbers. There is also a Lucas Lehmer Riesel test for numbers of the form N=k 2^n 1, with 2^n > k, based on the LLT: see Lucas Lehmer Riesel test. There is also a… … Wikipedia
Lucas–Lehmer test — This article is about the generalized Lucas–Lehmer test for primality. There is also a Lucas–Lehmer test that only applies to Mersenne numbers; see Lucas–Lehmer test for Mersenne numbers. In computational number theory, the Lucas–Lehmer test is a … Wikipedia
Édouard Lucas — François Édouard Anatole Lucas (April 4, 1842 in Amiens October 3, 1891) was a French mathematician. Lucas is known for his study of the Fibonacci sequence. The related Lucas sequence is named after him. He gave a formula for finding the nth term … Wikipedia
Marden's theorem — A triangle and its Steiner inellipse. The zeroes of p(z) are the black dots, and the zeroes of p (z) are the red dots). The center green dot is the zero of p (z). Marden s theorem states that the red dots are the foci of the ellipse. In… … Wikipedia
Tarski's undefinability theorem — Tarski s undefinability theorem, stated and proved by Alfred Tarski in 1936, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics. Informally, the theorem states that arithmetical truth… … Wikipedia
John Lucas (philosopher) — John Randolph Lucas FBA (born 18 June, 1929) is a British philosopher. Overview As an undergraduate at Balliol College, Oxford, 1947 1950, Lucas studied first maths, then Greats (Philosophy and Ancient History), obtaining his MA in Philosophy in… … Wikipedia
Korselts Theorem — Eine Carmichael Zahl, benannt nach dem Mathematiker Robert Daniel Carmichael, ist eine spezielle eulersche Pseudoprimzahl, für die gilt: Eine Carmichael Zahl n ist pseudoprim zu allen Basen, die keine gemeinsamen Primfaktoren mit n haben. Jede… … Deutsch Wikipedia
Fermat's little theorem — (not to be confused with Fermat s last theorem) states that if p is a prime number, then for any integer a , a^p a will be evenly divisible by p . This can be expressed in the notation of modular arithmetic as follows::a^p equiv a pmod{p},!A… … Wikipedia
Takens' theorem — In mathematics, a delay embedding theorem gives the conditions under which a chaotic dynamical system can be reconstructed from a sequence of observations of the state of a dynamical system. The reconstruction preserves the properties of the… … Wikipedia

Academic Dictionaries and Encyclopedias

Lucas' theorem

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Lucas' theorem

Look at other dictionaries:

Share the article and excerpts

Direct link