组合数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进制表达式中同

数位上的两个数码之和都小于 7,所以 C 5: 1。 3。不能被 7整除 . (注：文I - 3]对此例的判断是错误的) .一

例 2试判断 C 1 6。 0和。。 C… S l a 是奇数还是偶数. 解 ( 1 )因为 1 6 0— 2 +2 一( 1 0 1 0 0 0 0 0 ) z, 8 4 0—2。+2。+2 +2。 ( 1 1 0 1 0 0 1 0 0 0 ) 2,不存在位于

特别地，当一2时，我们可以得到定理的直接推论，用它可判断 C:= t的奇偶性. 推论设非负整数 m的以素数 2为基的进位制数为 ( 2 ),即 m( 2 )一m 2 +m一。 2 +…+m, 2 +…+ml 2+mo,其中数 m ( i一0, 1,…, s )在

同一数位上的两个数码都

是 1,所以 C 1 6。 0是。。奇数；( 2 )因为 5 1 3=== 2。+1一( 1 0 0 0 0 0 0 0 1 ) 2, 6 8 8—

2 +2 +2 +2 一( 1 0 1 1 0 1 0 0 0 0 ) 2,存在位于同一数位上的两个数码都是 1,所以 c。 5 1 3。。是偶数.参考文献

{ 0, 1 )中取值；非负整数一m的以素数 2为基的进位制数为 (—m) ( 2 ),即(— m) ( 2 )一( n—) 2 + ( T/ - ) 一1 2一+…+ ( 7 z—m), 2+…+ ( 7 2一

1王连祥等.数学手册[ M] .北京：人民教育出版社， 1 9 7 9

) 1 2+(一 ) 0,其中数 (一m) ( i一0, 1,…,当m +( 7 z—m) <2 ( 一0, 1,…, s )时， 2不能

2曹才翰，沈伯英 .初等代数教程[ M] .北京：北京师范大学出版社， 1 9 8 6

s )在{ 0, 1 )中取值 . 整除 C:= l,即C为奇数 . 当存在某个， ( i一0, 1,…, 5 ),使 m+(, 2一(上接第 4 O页)

3王晓静. C:: I被素数整除判别法的改进 E J] .喀什师范学院学报， 2 0 0 4, 3

4陈传理.高中数学竞赛名师讲座 (下册 ) E i V 1] .武汉：华中师范大学出版社， 1 9 9 3

( 1 )首先设计一个等腰梯形 (考虑到曲线的对称性 ),上下两底的长度分别为 2和 4,底角为 6 0。 .再选定两个向量口一(。 _1, 2 ), 6一( 2,一1 )作

髓一o

口+o

6,商一一口一 6 .0 0

( 1 )试判断四边形 ABC D的形状并给出

为基底，把、 、茄分别用 n, b表示，即一4. )

理由； ( 2 )若双曲线过 C、 D两点，且以 A、 B为焦

口+要 6,一o

o

n+

0

6,茄一一 no

点，求双曲线的离心率；( 3 )四边形 ABC D能否为某抛物线 C的内接

一

÷6,显然Al= j通过向量加法运算可得，再由向量

的数量积计算出底角大小 .

四边形？若能，请重新建立适当的直角坐标系，借助于上述背景材料，求出抛物线方程

;若不能，请说明理由. 现在全国范围内都在实施新课程计划，教师的教学设计、教学方式、学生的学习方式都与从前

( 2 )考虑到该等腰梯形中两对角线长易求

I ACI:=: 2√ 3, J AC f+I B C I一2+2√ 3,若双曲线以 A、 B为焦点，且经过点 C,则其离心率易求 .至

此解析几何的份量还稍嫌轻.( 3 )由于解析几何是用坐标方法研究图形问

有很大不同.但同时我们也看到许多用于考试的试题仍然用的是旧的试题，有些是与新课程的理念、新课程的要求是相违背的.许多教师苦于手头

题，而上述图形在平面中具有不确定性，因此借助平移思想设计一个开放性的问题，即该四边形能否为某抛物线的内接四边形？ 至此一个创新题出炉了！已知 n一 (一1, 2 ), b一( 2,一1 ),在四边形

没有合适的题目，于是就直接照搬陈题、旧题，这里不是说陈题一无是处，其实只要平时留心观察，并进行探索，我们是可以编拟出适应新教材要求的试题的.

AB C D所在的平面内，若

一 4口+ 8 b,

参考文献

1王先进.例谈选择题的命制.数学通报， 2 0 0 7, 5