免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 组合数求余

求$C_{1234}^{2008}$除以7的余数
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
现充已死,エロ当立。
维基用户页:https://zh.wikipedia.org/wiki/User:Tttfffkkk/
Notable algebra methods:https://artofproblemsolving.com/community/c728438
《方幂和及其推广和式》 数学学习与研究2016.

回复 1# tommywong
$C_{1234}^{2008}$结果木系为0了么?怎么我看木懂的…

TOP

本帖最后由 realnumber 于 2013-11-8 07:35 编辑

就当$C^{1234}_{2008}=7k+m$,k,m为整数,$0\le m\le 6$
定理:$n!$中含质数p的次数为[$\frac{n}{p}$]+[$\frac{n}{p^2}$]+[$\frac{n}{p^3}$]+.....
证明:$n!=1\times 2\times 3 \times  ....\times n$含p的倍数有[$\frac{n}{p}$]个,含$p^2$的倍数有[$\frac{n}{p^2}$]个,.....见《数论导引》第16页.
所以[$\frac{2008}{7}$]+[$\frac{2008}{7^2}$]+[$\frac{2008}{7^3}$]=286+40+5=331
[$\frac{1234}{7}$]+[$\frac{1234}{7^2}$]+[$\frac{1234}{7^3}$]=176+25+3=204,
[$\frac{774}{7}$]+[$\frac{774}{7^2}$]+[$\frac{774}{7^3}$]=110+15+2=127,127+204=331


$6!=-1 \mod7$,                     
$2008=6   \mod7$                    $2008!=(-1)^{287}=-1   \mod 7$
$1234=2   \mod7$                     $1234!=(-1)^{176}\times 1 \times 2=2  \mod7$
$774=4   \mod7$                     $774!=(-1)^{110}\times 1 \times 2 \times 3 \times 4=3  \mod7$
可见等式$2008!=1234! \times 774! \times (7k+m)$---------两边约去$7^{331}$后,考虑被7除的余数,即$-1=2\times 3 \times m   \mod7$,得到$m=1$.----------此楼红色有问题,修正见12楼.

TOP

回复 3# realnumber

对2008!、1234!、774!取余时错了
他们都含因数7,被7整除

TOP

回复 4# tommywong

有这句
    两边约去$7^{331}$后,考虑被7除的余数

TOP

本帖最后由 tommywong 于 2013-11-7 22:56 编辑

回复 5# realnumber

对不起,抓错了地方。麻烦再看看这里
$2008!=(-1)^{287}$这里的287好像是286

TOP

回复 6# tommywong


    对,是286,但还得乘以1,2,3,4,5,6;
那么就是287了

TOP

回复 7# realnumber

噢,又看漏了......但他给的答案是6
http://www.mathchina.com/cgi-bin ... ic=18888&show=0

TOP

没看到,懒得注册~~~

TOP

回复 9# realnumber

例如C(14,7)=3432=2(mod7)
6!(1)6!(2)=6!6!(7k+m)(mod7)
感觉抽走了286,176,110个7后剩下了些东西还要处理
是不是应该把286,176,110换作331,204,127?

TOP

本帖最后由 realnumber 于 2013-11-7 23:37 编辑

回复 10# tommywong


    ---恩,是有问题

TOP

本帖最后由 realnumber 于 2013-11-8 07:48 编辑

设$f(n)$表示$n!$抽走7后的余数,
比如$f(15)=6!\times8\times9\times10\times11\times12\times13\times2\times15=(6!)^2\times2=(-1)^2\times2\mod7$
例如2008含7的倍数的因数依次是$1\times7,2\times7,....,286\times7$,则有$f(2008)=(-1)^{286}f(286)\times 6!=-f(286)\mod7$
那么$f(2008)=-f(286)=-(-1)^{41}f(40)=f(40)=(-1)^5f(5)\times 5!=-1    \mod7$
$f(1234)=2f(176)=2(-1)^{25}f(25)\times 1=-2f(25)=-2(-1)^3f(3) \times 4!=1   \mod7$
$f(774)=3f(110)=3(-1)^{15}f(15)\times 5!=-3f(15)=1      \mod7$
这样有$f(2008)=f(1234)f(774)m,  m=6$.

TOP

猜想:若素数$p\mid n,p\nmid m,n\ge m$,那么$p\mid C^m_n$

TOP

本帖最后由 tian27546西西 于 2013-11-8 13:08 编辑

此猜想是正确的.楼主的题如果知道一个定理是非常容易算到的.

设$$n=n_{k}p^k+n_{k-1}p^{k-1}+\cdots+n_{1}p+n_{0}$$
$$m=m_{l}p^l+m_{l-1}p^{l-1}+\cdots+m_{1}p+m_{0}$$
由于$p|n$,则有$n_{0}=0$,

由$p\nmid m$,则 $m_{0}>0$

$$\binom{n_{0}}{m_{0}}\equiv 0\pmod p$$

由Luca's Theorem 显然有
$$\binom{n}{m}\equiv 0\pmod  p$$

TOP

本帖最后由 realnumber 于 2013-11-9 09:19 编辑

http://en.wikipedia.org/wiki/Lucas'_theorem
搜索到了~~,或google"卢卡斯(Lucas)定理",---
http://www.omaths.com/bbs/dispbbs.asp?boardid=183&Id=2251
1234-1.jpg
2013-11-9 09:19
1234-2.jpg
2013-11-9 09:19

TOP

额,不用此定理也可以:一步就是注意
$$m\binom{n}{m}=n\binom{n-1}{m-1}$$

TOP

返回列表 回复 发帖