多项式除法解高次同余

●

解题技巧与方法

●静

●

多项或 除法獬高次余◎黄嘉威 (暨南大学信息科技学院数学系，广东 广州 5 1 0 6 3 2 )

【摘要】本文研究了高次同余的计算问题，利用公式和递推的方法，推广了多项式除法的结果。

除P .展开即：

【关键词】同余；费马小定理；组合数；多项式1 .引言

’

定理2 . 1 X m p s∑ (一 1 ) c . m p - ( p - 1 ) i ( m o d p )用一个例子比较一下这个递推式与欧拉定理 aE 1 (m0 d n) .¨

由费马小定理开始高次同余有了计算方法，欧拉定理

葺 2x一

(m0 d 7 ) 4 4暑

(m 0 d 72 )

把它推广到合数情况， C a r m i c h a e l函数更使同余运算更进一

前者能在更小次方的情况下递推，更多的情况下 m p小于( P一1 ) P一+m.

步.

本文将透过多项式除法让高次同余运算得到更大的发展.

要是用前者递推高次同余，没能一步过的话会很麻烦，欧拉定理却能一步过 .。 0o

2 .费马小定理的推广费马小定理，即当。与 P互素，且 P为素数时，有o1(m o d D) .

掌 2x 9 4一 B 8三 3 x 8 8— 2x B 2鲁… (m o d 72 ) o 0。暑

(m o d 7。 )

这意味着多项式一整除P…,也意味着 ( 一 )整定理 2 . 2

X m p+ ( p - 1 ) n g∑ (一 1 ) 一 c i… - I— l c m… - i x m p - ( p - 1 ) i ( m o d p m )““§ c +2一

c+ l (mo d 7 2)

￡ 1 6 6 x 一1 6 5x E 1 9 x 一1 8 x (m o d 7 )

n=0时为定理 2 . 1

假如X m P+ ( p - 1 ) k∑(一 1 ) c一 ci=1 i=I

( m o d p )成立，i=2

X m p+ ( P - 1 ) ( ￡∑ (一 1 ) c i+ - I f _ l c m+ - i一‘ ;C m… - I +∑(一 1 ) ~ C i… - 1一 l c“ m - i一‘’‘m;

m—I

∑(一 1 ) c m - I L

ii= I一

‘+∑ (一 1 ) c C m+ - i~=l

’‘

1

;(一 1 ) c m - I+∑(一 1 ) . ) (c m - I c 一 c c一+

”(m o d pm)

由于 (一1 ) c+ 一。 cc m - i~: c c ‘ c 一 c+c。

= (一I ) c

,接下来只需证明一条恒等式：

拆开后得到：( k+, ) ! m! (k+ ) ! ( +,, 1 ) ! ( k+ ) ! ( k+m+1 ) ! (i一1 ) ! ( k+1 ) ! (m— ) ! ( k+ i+ 1 ) ! ( m一1 ) ! ( k十1 ) ! i ! (m一 )! i ! k ! (m— i一1 ) ! ( 十 i+ 1 )!e (k+ i+ 1) m一 (m— )( +1 )= (k+ m+ 1)车 m+ m+ m— k m—m+ + i= i k+ m+ i .

3 .递推与组合数待定因为 P?= m! C,所以多项式 P (, m)必然整除对应的阶乘 m! . 定理 3 . 1 P 7 l ( 一1 ) ( x一2 )…( —m+1 ) g 0 ( m o d m! ) .考虑。z 3 x一2 x ( m0 d 6 ),经过两次递推得到同余次数小于 3的多项式：x E 3 x 一2 x ￡ 3(3 一2 x)一 2x; 7 x 一 6x §r n一 1

(mod 6) .

定理3 . 2必然存在常系数c 使得X n ∑c ( m o d m ! ) .由于存在着递推关系；O ( m o d m! ), 必然与次数小于 m的多项式模 m!同余.

待定后，当= 0时为 0,所以它必然是一个没有常数项的多项式.例如：数学学习与研究

2 0 1 5

●

解题技巧与方法稚 O’●

f 。~一f 。~一 n; ( m 0 d 2 I ) .r c 0= OL 4c 2+2 c 1+c 0=2

f c 0= OC

{ c 2+ c l+ c。= 1 一{ c 1= 2— 2 . - 1 _+ ( 2一 1 ) 。+ ( 2— 2 ) ( m o d 3『 ) .【 c 2= 2 一一1

口∞口(

1

一

:=.

l

c c 一 -c 一 … c曼一 z

目 一： 一： 一

。 )三 一 ; .目 I j ;。 目 .圭、一

推论3 . 4 x

∑C i;∑d l c 一。 ( m o d m ! ) n≥m一 10 0 .

o ~圭、

1

n U nunH U n U口 n H U (

例如：一 一

; (co )(1 )(1 )一

,

(m o d 2) .n Un U nH U

+ 1 c c:一。 c 一 ( - 1 ) ( : ); c一 ( 2 1 _ ); -+ c 2 - 1 ) ( x - 1 )] - c 2 一 2+ c z - 2" ) x ( o r o d 6 )代入/ 7,=2, 3可得 i 3 x一2 x ( m o d 6 ), E 7 x一6 x i ( m o d 6 ) .

【参考文献】 [ 1]潘承洞.数论基础[ M] .北京：高等教育出版， 2 0 1 2 .[ 2]韩士安，林磊.近世代数[ M] .北京：科学出版社， 2 0 0 9 . [ 3]黄婷，车茂林，彭杰，张莉.自然数幂和通项公式证明的新方法[ J] .内江师范学院学报， 2 0 1 1 . 8

(上接 1 O 3页 )

二、可化为常系数线性非齐方程的方程——欧拉方程的解法

将 Y, ( Y ) , ( Y ) 代人原方程比较系数，得一9 a t一9 b=t ..

欧拉方程的解块一般步骤是：先写出 拉方程的特征方程，并求出特征根；再求出其基本组解，最后写出原方程

…

一

告，

=一古 ‘ .

的通解 .如下例： 例解_

得①的通解为 ),=C。 e 5 t+C e~一百 1 e .故原方程的通

求解方程 X 2 Y 一 3 x y 一 5 y= X 2 l n x .这是一个欧拉方程，令 t:l n x,=e‘,则

yl= d

z =÷,,:, ), = ,,:+÷ y d t= ( y?一 y, ) '代入原方程，得

解为 ),= c 5+导一÷ l n .三、总结

高阶微分方程的问题一般比较复杂，在具体求解时应根据微分方程的特点，具体问题具体对待，将微分方程化为易于求解的形式，只有这样才能达到简化易解的程度 .

Y一 4 y:一5 y= t e . 和①对应的齐次方程为：

y一 4,,:一 5 y= 0 .1,

①【参考文献】 ②[ 1]G e o r g e F .s i m mo n s, S t e v e n G .k r a n t z .D i f f e r e n t i a l E q u a t i o n s: T h e o r y, T e c h n i q u e,a n d P r a c t i c e[ M] .B e i j i n g:t s i n g h ua u n i v e r s i t y p r e s s, 2 00 9.

②的特征方程为 r。一4 r一5=0,特征根为 r。=5, r=一

则②的通解为 Y=C。 e+C e~ . 设①的特解为 Y’=( a t+ b ) e,则( Y ) =e ( 2 a t+口+ 2 6 ), ( Y‘ )=e ( 4 a t+ 4+ 4 b ),

[ 2]时宝，黄朝炎.微分方程基础及其应用[ M] .北京：科学出版社， 2 0 0 7 .

[ 3]李瑞遐.应用微分方程[ M] .上海：华东理工大学出版社， 2 0 0 5 .

【学学习与研究

2 0 1 5 . 9

本文来源：https://www.bwwdw.com/article/ngzj.html