组合数Cn^m被素数整除的又一种判别法

维普资讯 http://

2 0 0 8年第 4 7卷

第 8期

数学通报

4 l

组合数 C被素数整除的又一种判别法吴跃生(华东交通大学基础科学学院 3 3 0 0 1 3 )

1问题的提出

判断组合数

是否被某素数整除这一问

由于 c:: l一—『 ! _一 — m丌！ ,当且仅当上述不等m

题，看似比较简单，但当 m, 及素数比较大时，问

式中的每一个不等式都取等号时， d不能整除c,当且仅当上述不等式中的有一个不等式等号不成立时， d能整除 C 7 . ( 1 )当存在某个 i, ( i一0, 1,…, ),使 m;+(一

题就变得较复杂了. E 1, 2],文E 3]给出了组合数被素数整除的一种判别法，本文将给出组合数 C:: l被素数整除的又一种判别法 .2 主要结果

) ≥d成立时，不妨设 i一是 ( O≤是≤s )时， m +

定理。

设 d为素数，

(一 m) ≥ d,而 m+(一 ) < ( i一 0, 1,…, k一1 )。m

, z—n s d + r _ l d +…+n r d +…+ 1 d+ o

( 0≤≤ d一 1, i一0, 1, 2,…, s, ≠0 )m=== m d十 m一1 d+…+ m, d+…+ 1 d

— m一‘ ’卜 +一 一 一‘ ’+…+++

+ 0 ( O≤ mf≤一 1, i=== 0, 1, 2,…, s )口

+ mk - 1 d 一 1一 ( + 1’+…+ mo d一 ( + 1 ),j

(— )一(一 ) d +(, z— ) 一 1 d r。+…+(一 m) d +…+ (一仇 ) l d+ (一 m ) 0

d 一‘

+ m一 1 d 一卜‘

+…+ m+ 1

( O≤(, z— m) f≤d一1, i一0, 1, 2,…, s ),则

≤寿≤ m d 一‘ + m一 1 d 一 一‘ +…++ 1+( d- -1 ) ( - 1+ d +…+d - ( k+ ’ ) 一 m d 一‘( - 1 )

当 mf+( 7 z— ) <d ( i一0, 1,…, s )时， d不能整除 C 7; 当存在某 i ( i

一0, 1,…, s ),使 m。+(一 ) ≥成立时， d能整除 C . 证明由文 E 4]知：在！的质因数分解式

+,一 1 d 一卜‘

+…+ m+ 1+

中， d的指数是[号]+[ ]+…+[ ]+… (其中E x]为高斯函数，表示不超过的最大整数 ),

一7 7 z d ~‘ ( 1一 d一‘

+ r一卜‘ ’+…+抖 1+ ) +…+^+ 1+1

< d 一‘ ’+ r _ 1 d 一 一‘

所以，[寿] [署]+…+[ ]+…,在 ( 一 ) !的质因数分…+, 理，[ ]一 (, z一 解式中， d的指数是[ ]+[ ]+…+ 同 ) 一 l d 一 一‘ +…+( n - m) + 1, [ ]+…’

在m !的质因数分解式中， d的指数是』了 m I+

++ ( 一1+ ( I" 1一

由高斯函数的性质可得下列不等式：

而寿一

…

[甜+ -[ ]≤[孙[暑]+[ ]≤ , +[]≤[孙…,

=( m+ ( 一 m) ) d 一‘ m) 一 1 )d 一卜‘ m) +。 )+

+ (

+…+ ( m+ 1+ ( 一+ ( 卜。+ ( 一

维普资讯 http://

4 2m) 1 )dT r/ ) n ) d一‘一

数学通报‘ +…+ ( 0+ ( 一

2 0 0 8年第 4 7卷第 8期+…+ ( 十 ( —

十( 一l十 ( — ) 一】 )d

m) )+( 一 +( n— m) 一 )一 +…+ ( m。+( n—’+ ( m一 1+ (, 2一 m) o )一 ( +( n - ) ) d + ( 1+ (, 2一 ) 一 1 )

( m+ ( n一 ) ) d 一 ) 一 1 )d 一 ‘

+…+ ( + 1+ ( 一

) + )+1+ 卜 _

+(一

+

d s - 1 k+…+ (十 ( 一 ) )≤参≤( +( n -m) )d

(一 ) 一 1 ) d 一。卜+…+ ( m0+ ( 一Ⅲ) n ) d~( 十

d - (一 l+( n - m) 一 1 )

十…+( + ( n- - m)

)+ ( d- -1 ) d

所以， (/ 7"/ +(一/ T/ ) ) d

’+( r _ 1+( 一

+…+ ( d -1 )~一( m+( n - m) )一 +( 一 1+( n - m) 一 1 ) d 一 一+…+ ()

m) 一 1 ) d 一 ‘ + ’+…+ ( m^+ 1+ ( 一 m) + 1 )+ 1

≤寿≤( +(, z— m) ) d强’+ ( 一l+(”一优) 1 )d ‘ +…+ ( + 1+ ( 一+ (~ 1 ) d 一 一 c + +…

+ ( 一 ) )+ ( d一

一( +( n - m) )一 +( 一 1+( n - m) 一 1 ) d 一 一+…+ (优^+ ( — m) )+ ( 1一d一‘ 、

) + )+1++ (一 1 ) d一‘ ’一

< ( m+( n- -m) )一+ ( 一】+( n- - m) 一】 )

(

+ ( 一 ) )d一 ¨十 ( m一1+ ( 一

d

+…+( + ( n - m) )+ 1

’

) 一 1 )d 一卜‘

+…+ ( } 1+ ( n一

) + )+1+( 一1 )一

三+ ( m一 1+ ( 一

[ ]一 ( + ( 一 ) )+ ( 一 t+ ( n—) s - I ) d 卜+…+ ( +(— ) )

(/ 7"/ + (一/ 7"/ ) ) d 一‘

/ T/ ) 一 1 )d卜‘ 叶。 ’+…+ ( + 1+ ( n— ) 十 1 )+1+( 1一 d一‘。 ) < ( + ( 一 ) ) d 一 + (/ 7/ 一 1+ ( 7/"一…

同理，[ ]一 + m +…+, [ ]一 (,厂 + (一 卜 ++(一 m),

) 一 1 )d 一 ‘ ’ _ +…+ ( T n + l+ ( 一) +1 )+ 1+ 1

所以，[ H暑]+[ ], 此，不等式 +[ ]≤ , [寿]一 ( ( 一 ㈩ m r + ( — 因 m) 一 1 ) d r _ ~‘ +…+ ( m+ 1+ (, z—[暑]+[ ]≤[ ],…,[ ]+[]≤ m) + 1 )+1 [ ],…,中等号都同

时成立时， 不能整除 c _[寿]+[ ]+ 证毕. 定理可叙述为： ( ≤ )能否被素数 d整除≥[寿]+[ ] 取决于和 n~的 d进制表达式中同一数位上如果存在同一数位上的两个数即在不等式[ ]+[ ]≤[号],[暑]+ 的两个数码之和，所以，

[ n - m]≤[ ],…,[ ]+[]≤[ ],… 不能被素数 d整除.中至少有一个不等式等号不成立，所以 d能整除C . ( 2 )当+( n -m) < ( :0, 1,…, s )时，对任意的是， k f{ o, 1,…, ),有一 ( +(咒一 m) )

码之和不小于 d, 能被素数 d整除，否则例 1 试判断 C 5 1 3 能否被 7整除 .

就

维普资讯 http://

2 0 0 8年第 4 7卷第 8期

数学通报优)。一2成立时， 2能整除，即C:: l为偶数.

4 3

因为 5 1 3— 1× 7。+ 3× 7+ 3× 7+ 2一( I 3 3 2),,

推论也可叙述为： (≤ )的奇偶取决于 m 和n—m的二进制表达式中是否存在位于同一数位上的两个数码都是 1,如果存在， 是偶数，否则 C就是奇数 .

1 2 0 1—5 1 3—6 8 8— 2× 7。+ 0 X 7。+ 0× 7+ 2一

( 2 0 0 2 )

一5 1 3和—一6 8 8的 7进制表达式中同

数位上的两个数码之和都小于 …… 此处隐藏：2998字，全部文档内容请下载后查看。喜欢就下载吧 ……