一次同余式组的两种求解方法

同余

第27卷第4期2009年4月

文章编号：1004-3918（2009）04-0396-02

河南科学

HENANSCIENCE

Vol.27No.4Apr.2009

一次同余式组的两种求解方法

赵

摘

贞1，普丰山2，高丽1

（1.延安大学，陕西延安716000；2.漯河职业技术学院，河南漯河462002）

给出了求解同余式组的两种简便方法.要：运用矩阵的初等变换法和不定方程求解法，

文献标识码：A

关键词：同余式组；矩阵；不定方程中图分类号：O156.4

长久以来，求解同余式组的方法大多都是用孙子定理[1-2]，国际上称之为中国剩余定理．但用孙子定理

求解同余式组并不简便，且计算过程也比较繁琐．本文给出用矩阵的初等变换[3-4]和不定方程来求解同余式组[5]，它们有时比用中国剩余定理求解同余式组要简便得多．

定理1设同余式组

≡

≡≡≡≡≡≡≡≡≡≡

x≡a（，1modm1）x≡a（，2modm2）x≡a（．kmodmk）…

（1）

其中：（mi，mj）=1（i≠j），i，j=1，2，…，k，作矩阵

≠

≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠

M1M1a1M2M2a2…MkMkakM0

…

A=

≠

≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠

，

M=m1m2…mk；Mi=M/m（2，…，k）．其中：ii=1，

对A施行初等行变换，则矩阵A的某一行总可以变为（1，x0）的形式，此时同余式组（1）的解为x=x0（modM）．证明

因为（M1，M2，…，Mk）=1．所以存在整数u1，u2，…，uk，使得

1=u1M1+u2M2+…+ukMk，x0=u1a1M1+u2a2M2+…+ukakMk．

j≠i

（2）（3）

给定0≤i，j≤k，当i≠j时，mi│Mj，从而ujMj=0（modmi），由（2）式ΣujMj+uiMi=1有uiMi=1（modmi），代入（3）式得

x0=ΣajujMj+aiuiMi=Σ0（modmi）+a（，imodmi）

j≠i

j≠i

从而x=x0满足同余式组（1）的每一个方程，再由孙子定理的唯一性知，同余式组（1）有唯一解x≡x0（modM）．

定理2对于同余式组（1），设M=m1m2…mk，若m1，m2，…，mk是两两互素的正整数，又不定方程组

x=a1+m1t1=a2+m2t2=…=ak+mktk，t（2，…，k）∈Zii=1，

（4）

收稿日期：2008-11-25

基金项目：国家自然科学基金资助项目（10271093）；陕西省教育厅专项科研计划项目（07JK430）作者简介：赵贞（1964－），男，陕西延安人，高级经济师，从事经济数学方面研究通信作者：高丽（1966－），女，陕西绥德人，教授，硕士，从事解析数论研究.

同余

2009年4月赵贞等：一次同余式组的两种求解方法

-397-

有一特解x=x0，则同余式组（1）的解为x≡x0（modM）．

证明易知同余式组（1）等价于不定方程组（4）．

由（4）式可得

kx-m1x1-m2x2-…-mkxk=a1+a2+…+ak，

（4）式有解，亦即同余式组（1）有解．当（5）式有一特解x=x0时，对不定方程组（4）有解x=x0+Mt（t∈Z），则

）-ai=（x0-ai）+Mt=miti+Mt，i=1，2，…，k，（x0+Mt

显然有m│（i=1，2，…，k），即x≡x0（modM）是同余式组（1）的解．imiti+Mt参考文献：

［1］潘承洞，潘承彪．初等数论［M］．北京：北京大学出版社，1992．［2］闵嗣鹤，严士健．初等数论［M］．北京：北京高等教育出版社，1982．［3］北大数学系．高等代数［M］．北京：高等教育出版社，1978．

［4］杨家骐，王卿文．高等代数在初等数论中的应用［M］．济南：山东教育出版社，1992．

［5］宋道金，赵文玲，张明亮．初等变换的系列应用［J］．山东师范大学学报，1997，12（2）：210－213．

（5）

m1，m2，…，mk是两两互素的正整数，从而（m1，m2，…，mk）=1，故（k，m1，m2，…，mk）=1，因此（5）式有解，从而

TwoMethodsofSolvingLinearCongruenceEquationsSystem

ZhaoZhen1，PuFengshan2，GaoLi1

（1.Yan’anUniversity，Yan’an716000，ShaanxiChina；2.LuoheVocationalTechnicalCollege，Luohe462002，HenanChina）

Abstract：Inthispaper，bytheelementarytransformationofmatrixanddiophantineequation，twosimplemethodsofsolvinglinearcongruenceequationsystemarepresented．

Keywords：congruenceequationsystem；matrix；diophantineequation

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