初等数论吧 关注:798贴子:2,192

组合数的同余性质

只看楼主收藏回复

如果用C(n, m)= n!/ m!(n-m)! 表示组合数或者二项式系数
⑴ Lucas定理:
设p是素数,非负整数m, n, a, b, c, d 满足m = a×p+c,n = b×p+d,0 ≤ c, d ≤ p-1
① 若 a≤b 且 c≤d,则C(n, m)≡C(b, a)×C(d, c) (mod p)
② 若 a>b 或 c>d,则C(n, m)≡0 (mod p)
⑵ Wolstenholme定理:
设p是素数,非负整数m, n, a, b满足m = a×p, n = b×p,a≤b
则 C(n, m)≡C(b, a) (mod p³)


IP属地:北京来自Android客户端1楼2024-04-29 12:05回复
    帮顶一下!


    IP属地:广西来自Android客户端2楼2024-04-29 14:16
    收起回复
      吧友忠诚度这么低,说的肯定是你内容只有6分也是因为你的帖子太无聊了


      IP属地:北京来自iPhone客户端3楼2024-04-30 07:07
      收起回复
        你要不要考虑做一点浅显易懂的科普贴


        IP属地:北京来自iPhone客户端4楼2024-04-30 07:08
        回复
          还有Wolstenholme定理的推广:
          (Jacobsthal 1952):对于a>b>0,p>3,有C(pb,pa) ≡C(b,a)(mod p^q),其中q=3+Vp(ab(a-b))


          IP属地:重庆来自iPhone客户端5楼2024-05-01 12:26
          收起回复
            讲到Lucas定理,还可以说说经典问题(Fine定理):n是正整数,n0,n1,...nd是n的p进制表达式的数码,p是素数,那么在C (n,k),0≤k≤n中有(1+n0)(1+n1)...(1+nd)个数不是p的倍数。


            IP属地:重庆来自iPhone客户端6楼2024-05-01 12:42
            回复
              到后面再补上这些结论的证明过程之前想做成图片版,直接打字虽然不会有显示bug,但是格式看的有点乱


              IP属地:北京来自Android客户端7楼2024-05-01 12:48
              收起回复
                1. Lucas定理前半部分的直接证明


                IP属地:北京来自Android客户端8楼2024-05-02 21:40
                收起回复
                  2. 前半部分另一种构造多项式同余的证明



                  IP属地:北京来自Android客户端9楼2024-05-02 21:46
                  回复
                    3. Lucas定理的后半部分可以直接用Legendre公式证明


                    IP属地:北京来自Android客户端10楼2024-05-03 01:46
                    收起回复
                      4. Lucas定理的另一种形式和推论
                      推论1的充分性由(1)可得,必要性由(2)可知
                      它其实是Kummer定理的直接推论,而且对情形(2),Kummer定理精确的给出被p整除的次数
                      由这个介于Lucas定理和Kummer定理之间的重要推论,可以得到推论2


                      IP属地:北京来自Android客户端11楼2024-05-03 08:54
                      回复
                        5. Wolstenholme定理的几种等价形式
                        主楼的条件写漏了,得要求素数p>3


                        IP属地:北京来自Android客户端12楼2024-05-03 14:24
                        回复
                          6. Wolstenholme定理的一种证明
                          先证明⑵⑶⑷,再推出Ljunggren同余式



                          IP属地:北京来自Android客户端13楼2024-05-03 14:28
                          回复
                            注: Wolstenholme定理中,关于数论倒数与调和级数的关系


                            IP属地:北京来自Android客户端15楼2024-05-03 16:04
                            回复
                              7. Wolstenholme定理的另一种证法
                              在这个贴子
                              网页链接
                              直接用数论倒数的性质证明⑵⑶,再后面证明⑷⑸可以和前一种证法类似


                              IP属地:北京来自Android客户端16楼2024-05-03 16:27
                              回复