$C_{2p}^p=2 \mod p^2$

hbghlyj

hbghlyj 发表于 2024-11-5 13:56
我尝试的证明，请检查是否正确？ ...

在这个证明中,没有用到条件$p\nmid k$吧？所以这不可能是正确的！哪一步错了？

abababa

hbghlyj 发表于 2024-11-5 20:46
这一步是否有笔误？分子$(2p)!=(2p)!$相等，而分母不等吧。

原来如此，分子上$2p-1$乘到$p+1$，只有$p-1$项，应该是$(-1)^{p-1}$，阶乘约分了。
\[\binom{2p}{p}=\frac{2p(2p-1)\cdots(2p-p+1)p(p-1)\cdots(1)}{p^2((p-1)!)^2}\equiv\frac{2p^2(-1)^{p-1}(p-1)!(p-1)!}{p^2((p-1)!)^2}=2\pmod{p}\]

hbghlyj

hbghlyj 发表于 2024-11-5 13:59
在这个证明中,没有用到条件$p\nmid k$吧？ ...

$p$不整除$kp^m-x\over p^m-x$是否需要条件$p\nmid k$呢？

realnumber

hbghlyj 发表于 2024-11-6 21:27
$p$不整除$kp^m-x\over p^m-x$是否需要条件$p\nmid k$呢？

也不用。
假设整除，存在整数n,有$kp^m-x=p(p^m-x)n$,易得$p\mid x$
记$x=p^ty,p\nmid y,1\le t \le m-1$代入上式，得
$kp^{m-t}-y=p(p^{m-t}-y)n$,可得$p\mid y$矛盾.

realnumber

hbghlyj 发表于 2024-11-5 17:13
推廣：如果 $p$ 是素数，且 $a,b$ ($a\ge b$) 是任意正整数，则
$$\binom{pa}{pb}\equiv \binom{a}{b}\pmod ...

沿用4楼的办法证明5楼的推广
$(1+x)^{pa}=(1+x)^p(1+x)^{p(a-1)}$左右两边二项展开,其中$x^{pb}$的系数为
$C_{pa}^{pb}=C_p^0C_{p(a-1)}^{pb}+C_p^1C_{p(a-1)}^{pb-1}+C_p^2C_{p(a-1)}^{pb-2}+...+C_p^pC_{p(a-1)}^{p(b-1)}  \mod p^2$
右边除首尾两项都被$p^2$整除
可得$C_{pa}^{pb}=C_{p(a-1)}^{pb}+C_{p(a-1)}^{p(b-1)}  \mod p^2$
接下来配合数学归纳法似乎就可以证好了.

realnumber

$C_{ap}^{bp}=C_a^b \mod p^3$似乎还是可以沿用以往做法,如下:
p>3为素数,a,b为正整数,a>b
其实是打算$(1+x)^{ap}=(1+x)^{p}(1+x)^p(1+x)^{(a-2)p}$两边二项展开,不太好表达,先按以下展开
$(1+x)^{ap}=(1+x)^{2p}(1+x)^{(a-2)p}$两边二项展开,由$x^{bp}$的系数,可得
$C_{ap}^{bp}=\color{blue}{C_{2p}^0C_{(a-2)p}^{bp}}+\color{green}{C_{2p}^{1}C_{(a-2)p}^{bp-1}+...+C_{2p}^{p-1}C_{(a-2)p}^{(b-1)p+1}}+\color{blue}{C_{2p}^{p}C_{(a-2)p}^{(b-1)p}}+\color{green}{C_{2p}^{p+1}C_{(a-2)p}^{(b-1)p-1}+...++C_{2p}^{2p-1}C_{(a-2)p}^{(b-2)p+1}}+\color{blue}{C_{2p}^{2p}C_{(a-2)p}^{(b-2)p}}$
若绿色两部分
$\color{green}{C_{2p}^{1}C_{(a-2)p}^{bp-1}+...+C_{2p}^{p-1}C_{(a-2)p}^{(b-1)p+1}}=0 \mod  p^3$---(1)
$\color{green}{C_{2p}^{p+1}C_{(a-2)p}^{(b-1)p-1}+...++C_{2p}^{2p-1}C_{(a-2)p}^{(b-2)p+1}}=0\mod p^3$---(2)都成立
则蓝色部分$C_{ap}^{bp}=\color{blue}{C_{2p}^0C_{(a-2)p}^{bp}}+\color{blue}{C_{2p}^{p}C_{(a-2)p}^{(b-1)p}}+\color{blue}{C_{2p}^{2p}C_{(a-2)p}^{(b-2)p}}(??=C_{a-2}^{b}+C_2^1C_{a-2}^{b-1}+C_{a-2}^{b-2}) \mod p^3$成立,??处,接下来对a,b用数学归纳法证明,完.

以下证明绿色部分(1),其中$C_{2p}^i=C_p^0C_p^i+C_p^1C_p^{i-1}+...+C_p^iC_p^0=2C_p^i \mod p^2,i=1,2,3,..,p-1$
$C_{(a-2)p}^k=\frac{(a-2)p}{k}C_{(a-2)p-1}^{k-1},k=bp-1,bp-2,...,(b-1)p+1$(这些k都有 $k\nmid p$)
$C_p^i=\frac{p}{i}C_{p-1}^{i-1},i=1,2,3,..,p-1$

如此要证明(1)成立,只需要证明
$\sum_{i=1}^{p-1}\frac{(a-2)}{i(bp-i)}C_{p-1}^{i-1}C_{(a-2)p-1}^{bp-i}=0 \mod p$,分母理解为逆元,以下同.或参考6楼的习题2

由Lucas定理$C_{(a-2)p-1}^{bp-i}=C_{a-3}^{b-1}C_{p-1}^{p-i} \mod p$,

只需要证明$\sum_{i=1}^{p-1}\frac{1}{i^2}C_{p-1}^{i-1}C_{a-3}^{b-1}C_{p-1}^{p-i}=0 \mod p$

即只需证明$t\sum_{i=1}^{p-1}\frac{1}{i^2}C_{p-1}^{i-1}C_{p-1}^{i-1}=m(C_p^1C_p^1+C_p^2C_p^2+....+C_p^{p-1}C_p^{p-1})=m(C_{2p}^p-2)=0 \mod p$  $t=((p-1)!)^4,p\nmid m$
猜(2)大概也可以这样完成吧.

hbghlyj

realnumber 发表于 2024-11-8 06:47
Lucas定理也可以这样快速证明。分母理解为逆元

可以写一下吗

hbghlyj

我对定理 7.4 的证明中的一步有疑问：

hbghlyj 发表于 2024-11-5 12:08
$$
\binom{a p}{b p} \prod_{m=1}^b \prod_{k=1}^{p-1}(m p-k)=\binom{a}{b} \prod_{m=1}^b \prod_{k=1}^{p-1}[(a-b+m) p-k]$$

这一步怎么得到的？
我弄明白了：
将 $\binom{a}{b}$ 表示为连续整数的乘积，并将每个因子乘 $p$：
$$
\binom{a}{b}=\frac{a(a-1)\cdots(a-b+1)}{b!}=\frac{[a p][(a-1)p]\cdots[(a-b)p+p]}{[bp][(b-1)p]\dots b}
$$
此时分子分母均为公差为$p$的等差数列。每项后面增添$p-1$项，使其变成连续整数：
$$
\binom{a}{b}=\frac{\frac{a p(ap-1)\cdots(ap-bp+1)}{\prod_{m=1}^b \prod_{k=1}^{p-1}[(a-b+m) p-k]}}{\frac{(bp)!}{\prod_{m=1}^b \prod_{k=1}^{p-1}(m p-k)}}
$$
然后与 $\binom{a p}{b p}$ 进行比较：
$$
\binom{a p}{b p}=\frac{a p(a p-1)\cdots(a p-b p+1)}{(bp)!}
$$
等式得证。

realnumber

lucas定理,$\binom{a p+r}{b p+s}=\binom{a}{b}\binom{r}{s} \mod p$
p为素数，(a,p)=1=(b,p)，$ax=by=1\mod p$,记a,b的逆元$x=\frac{1}{a},y=\frac{1}{b}$,有这样性质$\frac{1}{a}\frac{1}{b}=\frac{1}{ab}$，比如$\frac{1}{1}\frac{1}{2}\cdots\frac{1}{p-1}=\frac{1}{(p-1)!}=\frac{1}{(p+1)(p+2)\cdots (p+p-1)}=\frac{1}{-1}=-1\mod p$
$0\le r<p,0\le s<p$
\[ \binom{a p+r}{b p+s}=\frac{1\times2\times\cdots\times{p-1}\times{\color{blue}{p}}\times \cdots\times{(ap-1)}\times{\color{blue}{ap}}\times (ap+1) \cdots \times(ap+r)}{\cdots\cdots}= \]
分子分母被p整除的蓝色部分，约去p后就是$\binom{a}{b}$,夹在kp之间的都约去，余留部分就是$\binom{r}{s}$,似乎你的28楼也是这样做的

hbghlyj

realnumber 发表于 2024-11-11 00:42
lucas定理,$\binom{a p+r}{b p+s}=\binom{a}{b}\binom{r}{s} \mod p$

能否用同样的方法证明Lucas定理推广到multinomial

$n=k_1+\dots+k_m$
multinomial${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}}$

是否成立${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}\equiv\prod_i\binom{n_i}{(k_1)_i,(k_2)_i\dots,(k_m)_i} \bmod p}$

hbghlyj

realnumber 发表于 2024-11-21 11:59
如果成立的话,ni,(km)i分别等于什么?

等于 $n$ 和 $k_m$ 在 p进制下的数字

hbghlyj

对 \( n = 1, \ldots, 6 \), \( k = 0, \ldots, n \), \( p = 5 \) 验证Lucas定理的Python代码：

1. def lucas_theorem(n, k, p):
2.     def binomial_mod(n, k, p):
3.         if k > n:
4.             return 0
5.         num = denom = 1
6.         for i in range(k):
7.             num = (num * (n - i)) % p
8.             denom = (denom * (i + 1)) % p
9.         return (num * pow(denom, -1, p)) % p
11.     def digits_in_base(n, base):
12.         digits = []
13.         while n:
14.             digits.append(n % base)
15.             n //= base
16.         return digits
18.     n_digits = digits_in_base(n, p)
19.     k_digits = digits_in_base(k, p)
20.    
21.     while len(k_digits) < len(n_digits):
22.         k_digits.append(0)
23.    
24.     result = 1
25.     for ni, ki in zip(n_digits, k_digits):
26.         result = (result * binomial_mod(ni, ki, p)) % p
27.     return result
29. p = 5
30. for n in range(1, 7):
31.     for k in range(n + 1):
32.         lhs = binomial(n, k) % p
33.         rhs = lucas_theorem(n, k, p)
34.         print(f"n={n}, k={k}, binomial(n, k) % p = {lhs}, Lucas' theorem = {rhs}, Verified: {lhs == rhs}")

复制代码

hbghlyj

hbghlyj 发表于 2025-1-13 13:01
能否用同样的方法证明Lucas定理推广到multinomial

$n=k_1+\dots+k_m$

对 \(m=3\), \(k_1,k_2,k_3 = 1, \ldots, 6 \), \( p = 7 \) 验证了这个“推广”，未发现反例。如何证明呢

1. from itertools import zip_longest
3. def binomial_mod(n, k, p):
4.     if k > n:
5.         return 0
6.     num = denom = 1
7.     for i in range(k):
8.         num = (num * (n - i)) % p
9.         denom = (denom * (i + 1)) % p
10.     return (num * pow(denom, p-2, p)) % p
12. def trinomial_mod(k1, k2, k3, p):
13.     return (binomial_mod(k1+k2+k3,k1,p)*binomial_mod(k2+k3,k2,p)) % p
15. def lucas_theorem_trinomial(k1, k2, k3, p):
16.     def digits_in_base(n, base):
17.         digits = []
18.         while n:
19.             digits.append(n % base)
20.             n //= base
21.         return digits
23.     k1_digits = digits_in_base(k1, p)
24.     k2_digits = digits_in_base(k2, p)
25.     k3_digits = digits_in_base(k3, p)
26.    
27.     result = 1
28.     for k1i, k2i, k3i in zip_longest(k1_digits, k2_digits, k3_digits, fillvalue=0):
29.         result = (result * trinomial_mod(k1i, k2i, k3i, p)) % p
30.     return result
32. p = 7
33. for k1 in range(1, 7):
34.     for k2 in range(1, 7):
35.         for k3 in range(1, 7):
36.             lhs = trinomial_mod(k1, k2, k3, p)
37.             rhs = lucas_theorem_trinomial(k1, k2, k3, p)
38.             print(f"k1={k1}, k2={k2}, k3={k3}, trinomial(k1, k2, k3) % p = {lhs}, Lucas' theorem = {rhs}, Verified: {lhs == rhs}")

复制代码

realnumber

hbghlyj 发表于 2025-1-22 01:28
对 \(m=3\), \(k_1,k_2,k_3 = 1, \ldots, 6 \), \( p = 7 \) 验证了这个“推广”，未发现反例。如何证明 ...

好像也可以沿用这样理解,如之前,特别当$r<s,\binom{r}{s}=0 \mod p$.
特别当$n_i<(k1)_i+(k_2)_i+\cdots+(k_m)_i,\binom{n_i}{(k1)_i,(k_2)_i,...,(k_m)_i}=0 \mod p$

hbghlyj

Cohomology Operations - Norman Earl Steenrod page 6