MathGoldMedalist
Sign InRegister

Lucas' Theorem

Lesson · Advanced

Number Theory: Combinatorial Number Theory

Lucas' Theorem

Let p be a prime. Write m and n in base p

m=mkpk+mk−1pk−1+⋯+m1p+m0m=m_kp^k+m_{k-1}p^{k-1}+\cdots+m_1p+m_0
n=nkpk+nk−1pk−1+⋯+n1p+n0n=n_kp^k+n_{k-1}p^{k-1}+\cdots+n_1p+n_0
0≤mi,ni<p0\leq m_i,n_i<p

Then

(mn)≡(mknk)(mk−1nk−1)⋯(m1n1)(m0n0)(modp)\binom{m}{n}\equiv\binom{m_k}{n_k}\binom{m_{k-1}}{n_{k-1}}\cdots\binom{m_1}{n_1}\binom{m_0}{n_0}\pmod p
Back to Toolkit