Lucas定理

• Code Level: 无
• Thingking Level: ※

Description：

$$\binom{n}{m} \equiv \binom{\ {\lfloor {\frac {n}{p}\ } \rfloor}\ }{\ {\lfloor {\frac{m}{p}\ } \rfloor}\ }*\binom{n\mod p}{m\mod p} \pmod{p}$$

Proof:

费马小定理可得：

$$(1+x)^n\equiv 1+x\equiv 1+x^n \pmod{p}$$ $$(1+x)^n=(1+x)^{\lfloor \frac{n}{p} \rfloor} *(1+x)^{n\mod p}$$

观察它们

$$x^m的系数$$ $$\binom{n}{m}=\binom{\lfloor \frac{n}{p} \rfloor}{i}*\binom{n\mod p}{j}(i+j=m)$$

则一定存在i，j使：

$$i=\lfloor \frac{m}{p} \rfloor\ ,\ j=m \mod p$$

得证

Delta

将上述Lucas定理看作递归的化可得：

$$\binom{n}{m}\equiv \prod_{i=1}^{i<=k} \binom{a_i}{b_i}\pmod {p}$$ $$a_i,b_i分别为p进制下的同位值$$