（基础数学专业论文）关于几类二项式系数和序列的同余性质.pdf

西北大学硕士学位论文 摘要 人们对二项式系数的研究已有近七百年的历史，通过长期的研究发现，二项式系 数和序列具有很多良好的性质，并且和许多数学问题有着非常密切的关系1 9 7 8 年 a p 百r y 利用二项式系数和序列的递推公式给出了( ( 2 ) 和( ( 3 ) 的无理性证明他的工 作极大的刺激了人们对二项式系数和序列的研究兴趣，从而取得了一系列新的研究成 果另一方面，随着密码学的发展，如何快速有效地寻找大素数成为人们研究的一个 热点2 0 0 4 年，由a g r a w a l ，k a 归l 和s a x e n a 给出的多项式时间的素数检测算法也与 某种类型的二项式系数和的同余性质有着密切的联系本文主要运用数论中的整除理 论、同余理论，对几种类型的二项式系数和序列的同余性质进行了研究 本论文的主要结果是： 一首先研究了二项式系数和序列d ( 礼) = ：。( ：) 2 ( ”毒) ，得出了d ( p ) ，d 一 1 ) ，d p + 1 ) ，d ( 印) 在模p 3 ，矿下的同余性质 二讨论了两种类型的二项式系数和序列 ：r = 。器扩和u 知 c ( 归猷_ 1 ) 叫扩( 秽( 计 证明了： 1 ： ：。， ： 二s ， ： ：在模p 下的同余性质，并得出了一些推论 2 u ： 6 ，。( 2 ) ，u ：，6 ，。( 3 ) ，u ： 6 ，。( 2 7 ) 分别在模2 3 ，3 3 ，2 新下的同余性质 这些结果的给出可以增加人们对这几类二项式系数和序列的认识，有利于相关问 题的进一步研究 关键词：同余；模；素数；二项式系数 西北大学硕士学位论文 a b s tr a c t c o n g r u e n c ep r o p e r t i e sf o rt h es u mo fb i n o m i a l ，” c o e m c l e n t s b i n o m i a lc o e 伍c i e n t sh a v eb e e ns t u d i e df o ra b o u t7 0 0 ”盯s p e o p l ef i n dt h a tt h e s u mo fb i n o m i a lc o e 伍c i e n t sh a v em a n yg o o dp r o p e r t i e sw h i c ha r er e l a t e dt om a n y m a t h e m a t i c a lp r o b i e m s i n1 9 7 8 ，a p 百r yp r o v e dt h ei r r a t i o n a l i t yo f ( ( 2 ) a n d ( ( 3 ) u s i n g t h er e c u r r e n c ef 曲t h es u mo ft h eb i n o m i a lc o e m c i e n t s s i n c et h e n ，m a n yp e o p l ep a y a t t e n 七i o nt ot h es u mo fb i n o m i a lc o e f i i c i e n t s s oal o to fn e wr e s u l t sa r eo b t a i n e d o n t h eo t h e rh a n d s ，w i c ht h ed e v e l o p m e n to fc r y p t o l o g y ，i ti sah o tt o p i ct h a th o wt of i n d ab i gp r i m ee 艉c t i v e l yi nr e e e n ty e a u r s i n2 0 0 4 ，ap 0 1 y n o m i a lt i m ep r i m a l i t yt e s t 髑 西v e nb ya g r d ，k a y 出a n ds a x e n a ，w h i c hi sr e l a t e dt ot h ec o n g r u e n c ep r o p e r t i 箦o f 马 k i n do fs u mo fb i n o m i a lc o e 伍c i e n t s i nt h i sp a p e r ，w em a i n l ys t u d ys e v e r a lk i n d so f s u mo fb i n o m i a lc o e 伍c e n t s 、r i at h em e t h o do fd i 们s i b i l i t ya n dc o n g r u e n c e i nt h i sp a p e r ，w em a i n l yd i s c u s st h ef b u o w i n gp r o b l e n l s ： f i r s t l y ，w es t u d yt h es u mo f b i n o m i a lc o e f f i c i e n t sd ( n ) = ：o ( ：) 2 ( ”毒) ，a n d o b t a i nt h ec o n g r u e n c ep r o p e r t i e so fd ( p ) ，d p 一1 ) ，d ( p + 1 ) ，d ( 2 p ) m o d u l op 3 ，矿 s e c o n d l y ，t 帕k i n d so fs u mo fb i n o m i a lc o e h i c i e n t sa r ec o n s i d e r e d ： ：= 。篙“8 a n d u ： 。( 垆尚州。( 秽( 秒 a sar e s u l t ，w ep r o 、，et h a t ： t h ec 。n g r u e n c ep r 。p e r t i e s 。r ： 三。， ： ：， ： ：m 。d u ，。pa n ds 。m e d e d u c t i o n s 2 t h ec o n g r u e n c ep r o p e r t i e so ft 正：，6 ，c ( 2 ) ，乱：，6 ，c ( 3 ) ，：，6 ，c ( 2 7 ) r e s p e c t i v e l ym o d u l o 2 3 ，3 3 ，2 3 r t h e s er e s u l t s r i l l 百、，ep e o p l em o r ee 仟b c t i v ei n f o r m a t i o na b o u tt h e s ek i n d so fs u m o fb i n o m i a lc o e 伍c i e n t s ，w h i c hi su s e f u lf o rt h ef u r t h e rs t u d yo fr e l a t e dp r o b l e m s k e y w o r d s ：c o n g r u e n c e ；m o d u l e ；p r i m e ；b i n o m i a lc o e m c i e n t s 1 1 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：塞者幽 指导教师签名： 如5 年占月j z 日 劢水 o ，对于所有足够大的整数 p ，g ，不等式 ( ( 3 ) 一p 口i g 卅吖成立这里臼= 1 3 4 1 7 8 2 0 ( ( 2 ) 的无理性也是 用类似的方法证明 上述工作的重点和难点就是找出二项式系数和序列的递推关系，而这个关系则是 由二项式系数和序列自身的性质所决定的因而a p 芭r y 的工作极大的刺激了人们【9 卜 【1 5 】对于二项式系数和序列递推关系以及同余性质的研究 1 9 9 5 年，a l s c h m i d t 和袁进教授 1 6 】合作，通过研究二项式系数和序列 跏，= 砉( 莎 n o ，r 在模p 下的同余性质，得到了肆( 几) 所能满足的多项式递推公式的一个非平凡下界， 即不存在非平凡整系数多项式r ( n ) ，只( n ) ，使得岛( n ) s m + 1 ) + p 1 ( n ) s ( 佗) = o 成 立 这里岛( n ) = c o + c l n + + c m 礼”，b ( 礼) = d 0 + d l n + + d 竹1 礼” 之后，袁进教授和她的学生【1 7 【1 8 】对序列s ( n ) 作了进一步的扩展，1 9 9 9 年， 袁进教授和h d i c l 【i n s o n 【1 9 】合作，给出了二项式系数和序列 口c n ，= 砉( z ) 加( 礼玄后) ”( n 志2 后) ”，珈，r - ，r t 为非负整数 c 3 ， 所能满足的多项式递推公式的下界估计 与此同时，一些学者 2 0 【2 1 对其它类型的二项式系数和的同余性质进行了研究： 2 0 0 5 年， m c h a m b e r l a n d 和k d i l c h e r 2 2 】给出了二项式系数和序列 吃如，= 扣严( 扰警) 6 七= o 、7 的一系列同余性质 2 0 0 6 年，z w s u n 和r t a u r a _ s o 2 3 】讨论了二项式系数和序列 2 ( 5 ) 、，n 后 ，一 m器。卦 v 肆专 的同余性质，对j w l g l a i s e r 的一个定理进行了推广 本文作者继续了以上的研究工作，共分三部分 第一章介绍本文相关的基础知识，并利用这些知识探讨了二项式系数和序列d ( n ) = ：o ( ：) 2 ( ”妒) 的同余性质 第二章研究了二项式系数和序列f 佗1 “，佗1 “，f 佗1 3 的同余性质，并利 l rj p l l r j p l r j2 p 用相关结论给出j w l g 1 a i s h e r 的一个定理的简洁证明及一些推论 第三章讨论了二项式系数和序列u ：，6 ，。( 礼) 的同余性质，给出了如下三个同余式 乱： 。( 2 ) 三1 + ( 一1 ) 2 6 3 。( m o d8 ) ，e o ，1 ) ； u ： 6 。( 3 ) 三1 + ( 一1 ) 2 6 3 。( m o d2 7 ) ，e o ，1 ) ； u ： ，。( 2 ) 三1 + ( 一1 ) 2 6 3 。( m o d2 3 7 ) ，e o ，1 ) 成立的充要条件 由于作者水平有限，论文中的漏洞和不妥在所难免，恳切希望专家和同行批评指 正 西北大学硕士学位论文 第一章基础知识 1 1 整除理论 本文主要运用了初等数论中的整除理论，同余理论以及二项式系数的相关知识 下面我们介绍本文涉及的相关内容 1 1 ，1 2 节相关知识参见【2 4 】 2 5 】 整除是初等数论的基础，它是对在小学就学过的整数的算术作抽象的系统的总 结，看起来似乎很简单，但是它的内涵是十分重要而深刻的这里给出一些本文相关 的整除的知识 1 带余数除法 设n ，6 是两个给定的整数，o o ，那么一定存在唯一的一对整数口与r ，满足 6 = 口n + 7 ，0 r io1 此外，n | 6 的充要条件是r = 0 2 设( 仇，n ) = 1 ，则有( m ，0 6 ) = ( m ，6 ) 证明：m = 0 时n = 土1 ，结论显然成立仇0 时， ( m ，6 ) = ( m ，6 ( m ，n ) ) = ( m ，( m 6 ，0 6 ) ) = ( 仇，m 6 ，曲) = ( 仇，n 6 ) 这就证明了所要的结论 3 设( 仇，o ) = 1 ，那么，若mn 6 ，则m 6 证明：i 仇l = ( m ，口6 ) = ( 仇，6 ) ，这就推出m 6 4 设p 是素数，那么 pi ( ：) ， 1s j p 一1 这里( ；) 表示组合数 证明：已知组合数 = 志 第一章基础知识 是整数，即歹! 一歹) ! l 正由于p 是素数，所以，对任意1 i p 一1 有，i ) = 1 因此由2 知， 0 ，歹! ( p j ) ! ) = 1 ，1 歹sp 一1 进而由3 推出：当1 歹p 一1 时，j ! p 一歹) ! lp 一1 ) ! 这就完成了证明 1 2 同余理论 同余理论是数论中一部分很重要的内容，同余概念的产生极大地丰富了数学的内 容本节将给出同余的概念和一些基本性质 定义( 同余) 设m 0 若mo 一6 ，即。一6 = 后m ，则称m 为模，口同余于6 模 m ，记作n 三6 ( m o dm ) ； 不然，则称。不同余于6 模m ，记作 n 6 ( m o dm ) 接下来给出同余式的几个性质： 性质1 同余是一种等价关系，即有 n 兰凸( m o dm ) ；o 三6 ( m o d 仇) 兮6 三n ( m o dm ) ； o 三6 ( m o dm ) ，6 兰c ( m o dm ) o 兰c ( m o dm ) 性质2 同余式可以相加，即若有 。三6 ( m o dm ) ，c 三d ( m o dm ) ，( 1 2 1 ) 则凸+ c 兰6 + d ( m o dm ) 性质3 同余式可以相乘，即若( 1 2 1 ) 式成立，则有 n c 三6 d ( m o dm ) 性质4 设d 1 ，dm ，那么，若同余式。三6 ( m o dm ) 成立，则 n 三6 ( m o dd ) 2 第一章基础知识 性质5 同余式 等价于 c 0 三c 6 ( m o d m ) n 三6 ( m o dm ( c ，m ) ) 特别的，当( c ，m ) = 1 时，同余式( 1 2 2 ) 等价于 下面给出关于同余式的两个引理： n 三6 ( m o dm ) 引理1 对任意素数p 和正整数七，歹，七歹， 证明：由于 又因为 所以 那么 ( 黝= ( 凳) 三( 多)( m o dp ) 印一( 咖+ m ) j p 一( 细+ m ) ( 多) 里籍期 0 竹l p 却一( 场+ m ) 如一( 加+ m ) 三1 ( m o dp ) ( 渤三( 多)( m o d p ) ( 1 2 2 ) 引理2 已知现1n ，6 2 2 o ，( 6 2 ，m ) = 1 ，若薪三r ( m o dm ) ，1 三t 2 ( m o dm ) ， 证明：由已知条件，可设 那么 导三r ( m o dm ) 瓦到( m o d m ) 云一r = m ，一。= 如m ，后，乜z n = 6 z l ( r + 尼1 m ) = 6 ( 乜m + z 2 ) ( r + 七1 m ) 三打z 2 ( m o dm ) 3 勰 珍一泗 ff 二一 一u 虫 0 第一章基础知识 由性质5 知 导兰r ( m o dm ) 瓦兰r ( m o d m ) 1 3 二项式系数相关定理 本节相关知识见参考文献 8 】 1 多项式定理设n 是正整数，z 1 ，z 2 ，z 是任意后个实变数，则 证明： ( z 1 + z 2 + + 钆) ”= n 1 + n 2 + + n k = 竹 ( t = 1 2 ， ) 是非负整数 佗l ! 钆21 礼!z ? 1 z 2 z ： ( z l + z 2 + + 巩) “是佗个因式( z 1 + z 2 + + z 詹) 的乘积，其展开式共有 护项我们可按如下方法将这些项进行分类：设甄。z i 。z i 。是展开式中任意一项， 如果在鼢1 ，z i 2 ，z “中有礼1 个z 1 ，n 2 个z 2 ，n k 个巩( n l + 几2 + + 礼七= 几) ， 则把黾，甄。z i 。归于伽1 ，扎2 ，n 七) 类显见属于( 竹1 ，佗2 ，n 七) 类的项的个数 等于有礼1 个z 1 ，n 2 个z 2 ，n 七个z 七做成的全排列数，为 t l l ! t 1 21 一n k ! ( z + z 2 + + z 岛) “的展开式中( 合并同类项之后) ，z ? 1 z ；2 z ：的系数为 所以定理的结论成立 2 二项式定理设n 是正整数，z 和可是任意实数，则 证明；由多项式定理，有 3 组合恒等式 ( z + 秒) 竹= 七= 0( z ) z k 耖”一南 ( 蚪y ) “= 如赢数高扩圹j 月 f m n = ：o 耐z y ”詹 = 趋。( ：) 矿圹 喜( 玑：后) = ( nn c 划 证明：因为( 1 + z ) ”( 1 + z ) ”= ( 1 + z ) ”棚，所以 砉( 垆薹 f ，? 、1 夕：宇 了 鲁 4 ，n + m 、， lr 尸 因此在 礼 n 11 n 21 n 七! 第一章基础知识 比较上式两边矿的系数得 喜( 扎：七) = ( nn 1 4 二项式系数和序列d ( 佗) 的同余性质 a p 百珂曾经指出二项式系数和序列d ( 礼) = ：o ( ：) 2 ( n ：) 满足递推关系n 2 d ( 几) 一 ( 几一1 ) 2 d ( 仃一2 ) = ( 1 1 佗2 1 1 佗+ 3 ) d ( n 一1 ) 这里，我们利用前面介绍的知识给出二 项式系数和序列d ，d p 一1 ) ，d p + 1 ) 在模矿，矿下的同余性质为了完成定理的 证明，我们首先给出几个引理 引理1 ( w 豳t e n h o l m e )若p 为素数，并且p 5 ，那么 ( 害二】 ) 三，( m o a 一 引理2 设m 为正整数，0 z 七，那么 ( m i1 ) = 静，( 尼：歹) 圳。( ：二 特别的( x 1 ) = 葛( 一1 ) 。( 己) + ( 一1 ) 七 证明：反复应用公式( ；嚣) = ( j ：。) + ( ；) 即可证明引理2 引理3 ( l u c a s )设亿= 他一1 n l n o 为几的以p 为底数的展开式，设尼= 克。昆。一1 克1 为克的以口为底数的展开式，那么 ( z ) 三n 函( 乏) c m 咖， 下面给出本节的主要定理及其证明 定理设p 为素数，那么以下同余式成立： ( i ) 当p 3 时，d 0 ) 三3 ( m o dp 3 ) ； ( 沈) d ( p 一1 ) 三：三：( p t 诎) ( m o dp 2 ) ； ( i i i ) 当p 3 时，d p + 1 ) 三3 ( 3 p + l + ( 雩1 ) ) ( m o dp 2 ) ； ( i t ，) d ( 2 p ) 三1 + ( 名) + 4 ( 害) ( m o dp 2 ) 5 第一章基础知识 定理的证明：首先证明( i ) 式 刊= 砉( 晰：尼) ( 习+ 蓦( 晰：后) = + 2 ( 翟二1 ) + 喜g ) 2 ( p ：七) 由引理1 可知，当p 5 时， ( 冒) 兰1 ( m o d 矿) ，所以 蚓三3 + 喜( 欺瑚m o a 矿， p 一1 ：3 + r j 二一 七= l p l ：3 + f j 二一 七= l 刚娄( 蚓 ( 州妻龇分- 注：以上推导利用了组合恒等式( ”毒”) = 冬。( ? ) ( 。! 。) 由于当1 i p 一1 时， pi ( ：) ，所以d ) 三3 + 2 三：( ：) 2 ( m o dp 3 ) 由范德蒙恒等式芝。( ：) 2 = ( 警) 和引理1 可得 俐三3 + ( 习- 2 ( m o a 内= + 2 ( 翟二】 ) 三3 ( m o a 以 另外，当p = 2 时，d ( 2 ) = ：o ( ：) 2 ( 2 之。) = 1 9 三3 ( m o d2 3 ) 当p = 3 时， d ( 3 ) = i ：o ( ：) 2 ( 3 ) = 1 4 7 兰1 2 ( m o d3 3 ) 因此对于素数p ，p 3 ，d p ) 三3 ( m o dp 3 ) 接下来证明( i i ) 式： m 叫= 篆p 万( 旷七= o 、 ，、， = 1 + 喜( p i1 ) 2 ( p 一三+ 后) 6 第一章基础知识 由引理2 上式可以转化为： d 仞一，= ，+ 喜 篓c 一，j ( 七兰歹) + c 一，t 2 ( p 一三+ 后) 烈扩d _ 1 + 喜【三卜d j ) 小1 ，jr 一去) 由于当1 i p 一1 时，pi ( ：) ，所以 d c p 一- ，三，+ 喜 2 萎c 一，( 七三歹) c 一，+ ( p 一三+ 七) c m 。d p 2 ， = 1 十2 喜霎c 一- ，( 后三j ) c 一，( p 一丢+ 七) + 喜( p 一：+ 七) c m 。d p 2 ， 而( p 一) = 垒型盟鲁业，由于当1 七p 一1 时，p10 1 + ) p 一2 + 七) p ， 但p t 七! ，所以pi ( p 一) 那么 d 。一，兰1 + 喜( p 一三+ 七) ( m o dp 2 ) = 篆“) c m 山2 i 采用类似的方法可以证明( i i i ) 式，下面给出( i v ) 式的证明 蛔，= 煮( 纵印：后) d ( 印) = ( ：) r ：尤) 七= 0 、。，、7 一( 筹) + 蕃( 吼印亨七) 而( 翟) = 型塾尘等吐业，当1 后p 一1 时，pi 印( 印一1 ) ( 印一七十1 ) ，但 p t 砧所以pi ( 碧) ；当p + 1s 七2 p 一1 时，矿l 印( 印一1 ) ( 印一七+ 1 ) ，但pl i 后! ， 所以pl ( 翟) 因此 蝻闰+ ( 篆) + ( 习2 ( 习c m 山2 一 由引理1 ，当p 5 时， ( 翟) 2 = ( 警) 2 ( 冒) 2 三4 ( m 。dp 2 ) ，所以 d c 2 p ，三，+ ( 荔) + 4 ( 害) c m 。d p 2 ， 第一章基础知识 当p = 2 时，d ( 印) = 1 2 5 1 兰3 ( m o dp 2 ) ；当p = 3 时，d ( 印) = 1 0 4 9 5 9 三 1 ( m o dp 2 ) 所以对于任意素数p ，d ( 2 p ) 三1 + ( 2 ) + 4 ( 翟) ( m o d 矿) 接下来利用本节定理给以下推论 推论 ( i ) d ( p 一1 ) 三1 ( m o dp ) ； ( i i ) 当p 3 时，d ( p + 1 ) 兰9 ( m o dp ) ； ( i i i ) d ( 2 p ) 三1 9 ( m o dp ) 注：利用【1 9 】中的引理也可以得出以上三个同余式，这里我们应用本节定理给出 新的证明 推论的证明：考虑到当1 七p 一1 时，plp 一七) ，即可得到( i ) 式接下来 证明( i i ) 式 由引理3 ( 譬1 ) 三( ；) ( ：) = 2 ( m o d 力，结合定理的( i i i ) 式，d p 1 ) 三 3 ( 3 p + 1 + 2 ) 三9 ( m o dp ) 采用同样的办法可以证明推论的( i i i ) 式 8 西北大学硕士学位论文 第二章 二项式系数和序列 ： 竺的同余性质 2 1引言 素数在许多数学问题，特别是数论中起着非常重要的作用国内外许多学者致力 于素数性质的研究，特别是如何去判断一个数是否为素数因为随着电子计算机和通 信网络的广泛应用，一方面为人们的生活和工作提供了极大的方便，另一方面也提出 许多亟待解决的问题，其中信息安全就是一个突出问题因此密码学理论和技术已成 为信息科学和技术中的一个重要研究领域r s a 公钥密码体制是一种安全性能良好 的密码体制，如何安全有效的生成大素数是密码系统的一个重要问题 2 0 0 4 年，m a g r a w a l ，n k a y a l 和n s a x e n a 【2 6 】 2 7 】给出的素数判定算法中，( z + o ) n 三扩+ nm o d ( n ，z ”一1 ) 起着核心作用而我们知道【2 3 】，若口，6 z ，口，m ，佗z + ， 那么 ( z + o ) ”兰矿1 + 6m o d ( g ，z m 一1 ) 一 三= r = 0 ： o o ，( g ，m ) = 1 ，n z ，并且满足9 谢( 1 一( 一o ) ”，g ) = 1 或者 n 三一1 ( m o d 口) 或者n 三1 ( m o dg ) ，2m ，那么 佗+ ? 国 。 ) 三 ： 。( 。) ( m 。d q ) ( 2 1 3 ) 其中g = p 1 赡。，( 口) = 囟 1 - 1 ( 钟1 1 ) ，p 芋。一1 ( 绔一1 ) 】，觑为使得疵兰 1 ( m o dm ) 成立的最小正整数t 这里作者主要研究以下二项式系数和序列： 眦= 的同余性质，并给出了j w l g 1 a i s e r 的一个结论，即( 2 1 2 ) 式的一个非常简洁的证 明，同时给出了一些推论 2 2 定理及其证明 定理 设n z + ，礼= f 印+ 殉，其中伯为模p 的最小非负剩余，我们可以得到 如下几个同余式： ( 。当r f 。时， ： ：。三垒。 ( 2 i ) ( 翟) ) 。( m 。d 力 ( 钇) 当r 珊时， y 三( ? ) 8 龇) 5 ( m o d 础 1 0 一m r 。时， ： ：三。( m 。d p ) 这里 佗】表示n 的整数部分 定理的证明： f n 1 ( s ) 【rl 。 ，佗、。 u ，f o p + l 七伽) 5 由恒等式( 1 + z ) 如升加= ( 1 + z ) 。o p ( 1 + z ) r o ，我们可以得到 利用( 2 2 1 ) 式 ，f 印+ 7 o 、 l 后 咒= ( ? ) ( 0 i ) 妻( 撇埘 又因为矿+ 1 i ( 卸) ( 幻一1 ) ( 切一渤+ i ) + 1 ) ，但矿+ 1 t ( 如+ i ) ! ，所以 i ) 三。 ( m o dp ) 其中0 j 伯时， f n 11 三o ( m o dp ) ； l ，j 印 当r r 。时，借助同余式( j 髯i ) 三o ( m 。dp ) ，其中o 歹 七， 1 i 鼽可以 得到 ： ：三( ? ) 8 坠，2 1 ( 袈) 8 ( m 。d p ) 注：本节定理的给出将使得计算以上几种类型的二项式系数和在模p 下的余数变得 很方便，有利于二项式系数和的研究例如序列 ： ：1 ，当佗= 7 5 9 3 ，p = 1 5 1 1 时，若要 计算 7 ；：s 譬。，直接应脆义式则需计算 7 黝：。= ：。 ( 1 3 篇饿) m o d l 5 1 1 ) ， 计算量很大若通过定理只需计算 7 ：3 ：。= ：。 ( 。翌；) ( ；) ) 5 ( m o d1 5 1 1 ) ，这 计算量很大若通过定理只需计算li= 二 ( ，翌。) ( ：) ( m o d1 5 1 1 ) ，这 就使得计算很简便了 利用本节定理给出如下两个推论： 推论1 ( i ) 当凡三0 ( m o dp ) 时， f o 2 0 + 1 ； 7 = f o + 1 ； r = f o 在参考文献 6 】中，作者给出了f n 1 ( 。) 在模p 下的一个周期性公式，即( 2 1 2 ) 式， l 。j 孵 这里我们给出 ： ? 在模p 下的同余式的一个递推公式 推论2 设p 为素数，那么 r 卸卜2 叫( m o a 办 ( 2 2 2 ) 推论1 的证明首先证明 咒三 因为当江r 时，( ，! 。) = 1 咒三 接下来证明( i i ) 式当几兰 ，而当i 取其它值时( ，! ) = o ，所以 娄 ( r 三i ) ( ? ) ) 3 c m 。dp ， f o + l ； r = f o + 1 ； 1 + 培( m o dp ) ，r = f o 推论2 的证明 采用归纳法，利用定理的( i i ) 式当r r o 时，首先证明后= 1 的情形 1 3 、，、， p p d d o o m m ，fl、，l 0 1 晚 力 力 葩 d m 矾 伍 伍， 0 9 引 n 叭叫 当0 武 d “ 九 伯时， ： 二1 三。( m o d p ) ，因而对于素数p ，推论2 成立 虽然早在1 8 9 9 年，j w l g l a i s e r 就给出了如下同余式 佗+ ：一1 p 一。三 ： p 一，c m 。d p ， 但是他的证明是很繁琐的，这里我们应用本节定理给出此结论在r f o 时的一个简短 证明采用归纳法： 由于n + p 一1 = f o p + r 0 + p 一1 = ( f o + 1 ) p + 一1 ，那么 ：- 1 ：。三 r 一，1 z o + l 扛= 0陋 州 那么，当s = 1 时， ： p 一。三垒。 ( 2 t ) ( 鼍) ) ( m 。d p ) 当f o = 1 时， ( m o d p ) 几+ ：一1 p 一，三萋 ( ? 二? ) ( 亨1 ) ) 吼， 二 三鬈 ( 7 7 二于) ( 2 2 ) ) 霎肥+ ( r ! i ) c 埘 三鬈 ( ( 2 抄( ( ) ( m o d p ) ( m o dp ) 霎 ( r ! i ) ( ：) ) + 萎 三霎 ( 7 7 二? ) ( 2 专1 ) ) + 霎 ( ? 二? ) ( ：；) ) c m 。d p ， 1 6 然而，根据假设，我们只需证明 霎 ( r ! i ) ( i 二。) ) 三霎 ( ? 二孑) ( ：) ) c m 。d p ， ( 2 2 3 ) 式可以写成 萎) ( i 埘三霎忙雌：) ) 即 ：。 ( ，旦。) ( ：) ) 三蓦 ( o 三) ( 2 专1 ) ) ( m 。d p ) 而由假设( 2 2 4 ) 式显然是成立的 这就完成了j w l g l a i s e r 定理的证明 1 7 ( m o dp ) ( 2 2 3 ) ( 2 2 4 ) 西北大学硕士学位论文 第三章 二项式系数和序列饥缸c ( 佗) 的同余性质 3 1引言 w i l s o n 定理是指，若p 是素数，r 1 i 一，印一1 是模p 的既约剩余系，则有 r 1 - 印一1 三一1 ( m o dp ) 特别的有p 一1 ) ! 三一1 ( m o dp ) 另外可以证明w i l s o n 定理的逆命题也是成立的，所 以该定理可以用来判定一个数是否为素数 1 8 6 2 年，w 6 l s t e n h o l m e 【3 2 】证明了 ( 翟二】) ) 三( m o ap 3 ) 其中p 为素数，p 5 同时证明了，同余式( 葛) 三1 ( m o dn 3 ) 在n 1 0 9 时没有 合数解在文献【3 3 】的问题b 3 1 中，j p j o n e s 曾经提出。上述命题的逆命题是否成 立? ”，这是一个迄今尚未解决的问题乐茂华【3 4 】曾对以上问题进行了研究 2 0 0 6 年，m c h a i n b e r l a n d 和k d i l c h e r 【2 2 】在此问题的启发下，考虑了二项式系 数和序列 吃如，= 扣严( 扒翟) 6 似) 七= 0 、7、7 因为u ；1 ( 仃) 具有w b l s t e n h o l m e 定理相似的同余性质，即 _ l 正i 1 ( p ) 三一1 ( m o dp 3 ) 在这篇文章中，作者证明了：若为p 素数，那么 u ：6 0 ) 三1 + ( 一1 ) 2 6 ( m o dp 3 ) ，p 5 ( 3 1 2 ) 同时给出了“：，6 ( 2 ) ，u ：，6 ( 3 ) 分别在2 3 ，3 3 下的同余性质，并且对于u ： 6 ( 2 ) 给出了类 似的同余性质，指出使得式( 3 1 2 ) 式成立的数不一定是素数 1 8 这里作者对( 3 1 1 ) 式做了进一步的扩展，考虑二项式系数和序列 的一些同余性质 吒如= 静严( 扰纵警) 。 k = o 、，、7 3 2 定理及其证明 定理一n 0 ，6 0 ，c 0 ，e o ，1 ) ，那么同余式 让：，6 ，。( 2 ) 三1 + ( 一1 ) 2 6 3 。( m o d8 ) 成立，当且仅当t 1 6 2 ，2t 玩2 干c ，e = 1 ； 2 6 2 ，2f6 ，2lc ，e = o ； 3 6 = l ，q 1 或c 1 ，2tc ，= 1 ； 4 6 = 0 ，o 3 或c 3 ，2ic ，e = 0 ； 5 ( ，6 ，c ，e ) = ( 1 ，o ，2 ，o ) ，( 2 ，o ，2 ，o ) ，( 0 ，1 ，o ，o ) ，( 1 ，o ，o ，1 ) ，( 1 ，o ，l ，o ) ) 证明：由u ： 6 。( 仃) 的定义式 屹吣= 扣广( 丢) 谢( 芝) 。 七= o 、7、7 ：1 + ( 一1 ) 2 ( n + 2 c ) 3 c + 2 6 3 。3 6 5 。 下面我们分两种情况进行讨论： 情况1 当8 + 2 6 + c 3 ( 记作条件( 3 2 ，2 ) ) 时， 乱三6 。( 2 ) 三1 + 2 6 3 。3 6 5 。( m o d8 ) ( 3 2 1 ) 如果6 2 ，条件( 3 2 2 ) 当然成立，此时若要( 3 2 1 ) 式成立，那么3 6 5 。三( 一1 ) ( m o d8 ) 当= 1 时，3 6 5 。三一1 ( m o d8 ) ，由于当2 ”时，3 6 三3 ( m o d8 ) ；当2i6 时， 3 6 三1 ( m o d8 ) ；当2tc 时，5 。三5 ( m o d8 ) ；当2c 时，5 。兰1 ( m o d8 ) ，所以这里 应有2 十6 ，2 十c 1 9 第三章 二项式系数和序列仳： 。( n ) 的同余性质 当e = o 时，3 6 5 。三1 ( m o d8 ) ，那么2f6 ，2 c 如果6 = l ，要想使得条件( 3 2 2 ) 满足，那么o 1 或c l ，此时若要( 3 2 1 ) 式 成立，那么3 5 。三( 一1 ) ( m o d8 ) 当e = 1 时，3 5 。三一1 ( m o d8 ) ，根据上述讨论可得此时2tc 当e = 0 时，3 5 。三1 ( m o d8 ) ，这是不可能的 如果6 = 0 ，若要条件( 3 2 2 ) 成立， o ，c 的取值有以下几种情况：凸3 或 c 3 ；或n = 1 ，c = 2 ；o = 2 ，c = 1 ；n = 2 ，c = 2 此时若要( 3 2 1 ) 式成立，那么 5 。三( 一1 ) ( m o d8 ) 当e = 1 时，5 。三一1 ( m o d8 ) ，由前面的讨论知道这是不可能的 当e = 0 时，5 6 三1 ( m o d8 ) ，所以这里2i c 所以此时若要( 3 2 1 ) 式成立，有以下三种情况：o 3 或c 3 ，2lc ，e = o ； d = 1 ，c = 2 ，= 0 ；o = 2 ，c = 2 ，= 0 情况2 当0 口+ 2 6 + c 2 时，( n ，6 ，c ) 的取值如下： ( o ，务，c ) = ( o ，o ，o ) ，( o ，o ，1 ) ，( o ，1 ，0 ) ，( 1 ，o ，o ) ，( 1 ，o ，1 ) ，( 2 ，o ，o ) ，( o ，o ，2 ) ) 如果( o ，6 ，c ) = ( o ，0 ，o ) ，让：6 ，。( 2 ) = 2 + ( 一1 ) 当e = o 时，t l ：，6 ，。( 2 ) = 3 ，可见( 3 2 1 ) 式不成立当= 1 时，锃：，6 ，。( 2 ) = l ，可 见( 3 2 1 ) 式不成立 如果( n ，6 ，c ) = ( o ，1 ，o ) ，u ： 6 。( 2 ) = 7 + 4 ( 一1 ) 当e = o 时，钆：b 。( 2 ) 兰3 ( m o d8 ) ，可见( 3 2 1 ) 式成立 当e = 1 时，u ：6 。( 2 ) 三3 ( m o d8 ) ，可见( 3 2 1 ) 式不成立 采用同样的方法讨论剩余的情况，只有当( 凸，6 ，c ) = ( 1 ，0 ，0 ) ，e = 1 ；( n ，6 ，c ) = ( 1 ，o ，1 ) ，e = o 时，( 3 2 1 ) 式成立 综合上述情况就完成了定理一的证明 定理二若n o ，6 o ，c o ，e 0 ，1 ) ，那么 u ： 6 。( 3 ) 兰1 + ( 一1 ) 2 6 3 。( m o d2 7 )( 3 2 3 ) 成立，当且仅当； 1 c 2 ，36 ，e o ，1 ) ； 2 c = 1 ，o 1 或6 1 ，36 ，e o ，1 - ； 2 0 3 c = o ，n 3 或6 3 ，36 ，e o ，1 】r ； 4 ( 口，6 ，c ，e ) = ( o ，o ，o ，1 ) ，( 1 ，o ，o ，1 ) ，( 2 ，o ，o ，1 ) ，( 1 ，1 ，o ，o ) 证明：根据仳：曲。( n ) 的定义式 吃咖= 扣严( 城) 6 ( 芸) 。 = 1 + 3 。+ 2 c 【( 一1 ) 2 6 + 2 2 c 5 6 】+ ( 一1 ) 2 6 3 。2 2 。5 6 7 。 分两种情况进行讨论： 情况1 当n + 6 + 2 c 3 ( 记作条件( 3 2 4 ) ) 时， u ： 6 ，。( 3 ) 兰1 + ( 一1 ) 2 6 3 。 2 2 。驴7 c ( m o d2 7 ) ，若要( 3 2 3 ) 式成立，那么2 2 。5 6 7 。三1 ( m o d2 7 ) ，然而2 2 。5 6 7 。= 2 8 c 1 0 6 三1 0 6 ( m o d2 7 ) ，所以这里31 6 若要条件( 3 2 4 ) 成立，有以下几种情形：c 2 ；c = 1 ，口1 或6 1 ；c = 0 ， n 3 或6 3 ；另外( 口，6 ，c ) = ( 1 ，2 ，o ) ，( 2 ，2 ，o ) ，( 2 ，1 ，o ) ，也满足条件( 4 2 4 ) ，但是显然 不满足3i6 所以此时若要( 3 2 3 ) 式成立只有c 2 ，36 ；c = 1 ，o 1 或6 1 ，3i6 ； c = 0 ，o 3 或6 3 ，36 2 当0 n + 6 + 2 c 2 时， ( o ，6 ，c ) 的取值情况如下： ( o ，b ，c ) = ( o ，1 ，o ) ，( 1 ，1 ，0 ) ，( o ，2 ，o ) ，( o ，o ，o ) ，( 1 ，o ，o ) ，(