卢卡斯的定理

卢卡斯的定理二项式系数对质数的模的结果是什么 $p$。它会回答以下问题:

• 的 $米$而且 $n$是 $m \ binom {} {n}$即使是吗?
• 当a时余数是多少<一个href="//www.parkandroid.com/wiki/binomial-coefficient/" class="wiki_link" title="二项式系数" target="_blank">二项式系数就像 $\ binom {100} {30}$除以a<一个href="//www.parkandroid.com/wiki/prime-numbers/" class="wiki_link" title="质数" target="_blank">质数就像 $13$？
• 有多少项 $34 ^ \文本{th}$行<一个href="//www.parkandroid.com/wiki/pascals-triangle/" class="wiki_link" title="帕斯卡三角形" target="_blank">帕斯卡三角形是整除 $11$？哪些条目不是?它们对什么取余 $11$？

卢卡斯定理指出对于非负整数 $米$而且 $n$，和一个素数 $p$， ${m \选择n} \枚\ prod_ {i = 0} ^ {k} {m_{我}\选择n_{我}}\ pmod p,$在哪里 $m = m_ p {k} ^ {k} + m_ p {k - 1} ^ {k - 1} + \ cdots + m_ {1} p + m_ {0}$而且 $n = n_ p {k} ^ {k} + n_ p {k - 1} ^ {k - 1} + \ cdots + n_ {1} p + n_ {0}$是基础 $p$扩张的 $米$而且 $n,$分别。这里使用了约定 $m \选择n$= 0时 $m < n$。

特别是, $m \ binom {} {n}$是整除 $p$当且仅当至少有一个的基础, $p$数字的 $n$大于对应的底数- $p$数字的 $米$。

要看一个具体的例子，请举 $p = 2。$然后 $m \ binom {} {n}$是即使且仅当至少有一个的二进制位数 $n$大于对应的二进制数 $m。$所以, $\ binom {8} {3} = 56$甚至因为 $3 = 0011 _2$有一个比?大的数字 $8 = 1000 _2$(具体来说，是最右边的数字)。

另一个有趣的结果是 $m \ binom {2 ^ k - 1} {}$总是奇怪的，自从 $2 ^ k - 1$用二进制表示时都是1;例如, $m \ binom {31} {}$总是很奇怪。

最常见的问题之一是直接应用卢卡斯定理:a的余数是多少<一个href="//www.parkandroid.com/wiki/binomial-coefficient/" class="wiki_link" title="二项式系数" target="_blank">二项式系数当除以a时<一个href="//www.parkandroid.com/wiki/prime-numbers/" class="wiki_link" title="质数" target="_blank">质数？

求余数，当 $\ dbinom {1000} {300}$除以13。

---

我们首先把1000和300写成13的幂和: $1000 = 5 (13^2)+ 11(13) + 12 \quad \text{and}\quad 300 = 1(13^2)+ 10(13) + 1$然后应用卢卡斯定理: $\begin{aligned} \dbinom{1000}{300} \equiv \dbinom{5}{1} \cdot \dbinom{11}{10} \cdot \dbinom{12}{1} &\equiv 5\cdot 11 \cdot 12 \\& \equiv 5\cdot (-2) \cdot (-1) \\&= 10， \end{aligned}$意味着余数是10。 $_ \广场$

注意:看得更深一点，可以在帕斯卡三角形中进一步探索这些系数。

的条目数的公式 $n ^ \文本{th}$帕斯卡三角形中不能被整除的那一行 $p$的底数 $p$的扩张 $n$。

---

写 $N = N ^k + \cdots + n_0$， $R = r_kp^k + \cdots + r_0$。然后 $r \ binom {n} {}$不能被 $p$当且仅当 $le n_i r_i \$为 $0 \le我\le k$。有 $n_i + 1$选择为每个 $r_i$(它可以 $0 1 \ ldots n_i$)．所以答案是 $\ prod_ {i = 0} ^ k (n_i + 1)。\ _ \广场$

请特别注意if $n = p ^ {k + 1} 1$，然后所有的 $n_i$等于 $p 1$所以乘积是 $p ^ {k + 1}$；也就是说,所有 $p ^ {k + 1}$的项 $左(p \ ^ {k + 1} 1 \右)^ \文本{th}$不能被整除 $p$。

事实上，对于前面的例子，取 $p = 2$给出以下结果:

图片为 $p = 2$：如果我们画出奇数项的图 $n ^ \文本{th}$帕斯卡三角形的行( $p = 2$)，我们得到的图像看起来非常像<一个href="//www.parkandroid.com/wiki/fractals/" class="wiki_link" title="Sierpinski垫片" target="_blank">Sierpinski垫片：

来源:http://ecademy.agnesscott.edu/ ~ lriddle / ifs / siertri / pascalmath.htm

这种分形来自于一个事实，如果 $K \le a < 2^n$,然后 $k \ binom{一}{}\枚\ binom {+ 2 ^ n} {k} \枚\ binom {+ 2 ^ n} {k + 2 ^ n} \(文本{mod} \ \ 2)$根据卢卡斯定理，所以上面 $2 ^ n$下一行并排复制两次 $2 ^ n$行。
中间部分呢?这由表单的元素组成 $\ binom {+ 2 ^ n} {r},$在哪里 $A < r < 2^n$。在这种情况下，因为 $r >$的二进制位数中的至少一个 $r$会大于对应的二进制数 $一个$，所以这部分乘积在卢卡斯定理中是 $\ binom{0}{1} \枚0$，所以中间部分的所有项都是偶数。

表明, $\binom{n}{p} \equiv \左\lfloor \frac{n}{p} \右\rfloor \pmod p$。

---

让 $N = n_k p^k + \cdots +n_1 p +n_0$的扩展 $n$在基地 $p$。卢卡斯定理说 $p \ binom {n}{} \枚\ binom {n_1} 1 \ binom {n_0} \ 0枚n_1 \(文本{mod} \ \ p)$而且 $\左\lfloor \frac{n}{p} \右\rfloor = n_k p^{k-1} + \cdots + n_1 \equiv n_1 \pmod p$，所以两边相等。 $_ \广场$

有几种证明，但最接地气的是归纳法。这个想法就是写作 $n = Np+n_0, k = Kp+k_0$由<一个href="//www.parkandroid.com/wiki/division-algorithm/" class="wiki_link" title="辗转相除法" target="_blank">辗转相除法，然后证明这一点 $\ binom {Np + n_0} {Kp + k_0} \枚\ binom {N} {K} \ binom {n_0} {k_0} \ (p {mod} \ \文本),$在哪里 $0 \le n_0,k_0 < p$。这个结果之后是归纳法 $N, K$小于 $n, k$分别为，底为- $p$扩张的 $N$而且 $K$只是基础- $p$扩张的 $n$而且 $k$省略了最右边的数字。

为了证明上面的公式是正确的，把左边写成 $\压裂{(Np + n_0) (\ cdots) ((n - k) p + n_0-k_0 + 1)} {(Kp + k_0) !}，$把第一个分离出来 $k_0$上面和下面的项。这些都是 $\压裂{(Np + n_0) (\ cdots) (Np + n_0-k_0 + 1)} {(Kp + k_0) (\ cdots) (Kp + 1)}。$分母不能被整除 $p$，所以这是 $\ binom {n_0} {k_0} \ pmod p$。

剩下的项是连续的 $p$；在每一组 $p$上面和下面都有一项可以被整除 $p$，其余是每个非零元素mod的产品 $p$,即 $(p - 1) !$国防部 $p$。的 $(p - 1) !$在顶部和底部取消mod $p$，我们可以乘 $p$每一项都可以被整除 $p$。剩下的是 ${病例}\ \开始压裂{N (N - 1) (\ cdots) (N - K + 1)} {K !}和{如果}\ n_0 \ \文本通用电气k_0 \ \ \压裂{(n - 1) (2) (\ cdots) (n - K)} {K !} & \text{if} \ n_0 < k_0。\{病例}结束$所以我们得到 $k \ binom {n}{} ={病例}\ \开始binom {n} {k} \ binom {n_0} {k_0}和{如果}\ n_0 \ \文本通用电气k_0 \ \ \ binom {n} {k} \ binom {n_0} {k_0}和{如果}\ \文本n_0 < k_0, \{病例}$但在第二种情况下，它也等于 $K \ binom {N} {} \ binom {n_0} {k_0}$因为两者都是 $0$。根据归纳法，这个定理成立。 $_ \广场$