一个组合问题
记$C_n^m$表示从n个不同的球中选择m个方案数目.(当n<m时为0,而且$C_0^0=1$)p为素数
求证:
$C_n^m-=C_{n%p}^{m%p}C_{}^{}\quad (mod p)$
其中$a%b$表示a关于b的余数(范围在0到b-1之间),$$表示不超过x的最大整数 比较纳闷：有“同余”符号，但却不知“模”是多少？ 难道这里的 $-=$ 表示“恒等”？:Q:
令 $n=12, m=5, p=7$, 则：
左边$=C_12^5$,
右边$=C_5^5C_2^1=2$，
也不相等啊？ 漏了mod p了,已添加
不过你上面的例子中,p=7时,右边是$C_5^5C_1^0=1$而不是2 数论中一般的高斯函数定义为：用 $$ 表示不超过 $x$的最大整数；
你的主题帖中，与之并不同：$$ 表示不小于 $x$ 的最大整数。
估计是“笔误”吧？:) 错误太多了:loveliness: 为什么要强调p为素数？ 因为小肚子是素的 可以用母函数来证明：
设 $n%p =b_1,\quad=k_1$
$m%p =b_2,\quad=k_2$
$(1+x)^n=(1+x)^(k_1*p+b_1)=(1+x)^(k_1*p)*(1+x)^(b_1)=(\sum_{i=0}^{p}C_p^ix^i)^(k_1)*(1+x)^(b_1)$
因为p为素数，所以 $(\sum_{i=0}^{p}C_p^ix^i)^(k_1)*(1+x)^(b_1) -= (1+x^p)^(k_1)*(1+x)^(b_1)\quad (mod p) $
即$(1+x)^n -= (1+x^p)^(k_1)*(1+x)^(b_1)\quad (mod p) $
式子左边$x^m$的系数是$C_n^m$,式子右边$x^m$的系数是$C_(k_1)^(k_2)*C_(b_1)^(b_2)$
证毕。 发现这个就是组合里面的 <A href="http://en.wikipedia.org/wiki/Lucas'_theorem" target="_blank">Lucas定理</A>
页:
[1]
2