第四章第三节高次同余式的解数及解法

初等数论学习总结本课程只介绍初等数论的的基本内容。

由于初等数论的基本知识和技巧与中学数学有着密切的关系， 因此初等数论对于中学的数学教师和数学系(特别是师范院校)的本科生来说，是一门有着重要意义的课程，在可能情况下学习数论的一些基础内容是有益的．一方面通过这些内容可加深对数的性质的了解，更深入地理解某些他邻近学科，另一方面，也许更重要的是可以加强他们的数学训练，这些训练在很多方面都是有益的．正因为如此，许多高等院校，特别是高等师范院校，都开设了数论课程。

最后，给大家提一点数论的学习方法，即一定不能忽略习题的作用，通过做习题来理解数论的方法和技巧，华罗庚教授曾经说过如果学习数论时只注意到它的内容而忽略习题的作用，则相当于只身来到宝库而空手返回而异。

数论有丰富的知识和悠久的历史，作为数论的学习者，应该懂得一点数论的常识，为此在辅导材料的最后给大家介绍数论中着名的“哥德巴赫猜想”和费马大定理的阅读材料。

初等数论自学安排第一章：整数的可除性（6学时）自学18学时整除的定义、带余数除法 最大公因数和辗转相除法 整除的进一步性质和最小公倍数 素数、算术基本定理[x]和{x}的性质及其在数论中的应用习题要求3p ：2，3 ； 8p ：4 ；12p ：1；17p ：1，2，5；20p ：1。

第二章：不定方程（4学时）自学12学时二元一次不定方程c by ax =+多元一次不定方程c x a x a x a n n =++ 2211 勾股数 费尔马大定理。

习题要求29p ：1，2，4；31p ：2，3。

第三章：同余（4学时）自学12学时同余的定义、性质 剩余类和完全剩余系 欧拉函数、简化剩余系欧拉定理、费尔马小定理及在循环小数中的应用 习题要求43p ：2，6；46p ：1；49p ：2，3；53p 1，2。

第四章：同余式（方程）（4学时）自学12学时同余方程概念 孙子定理高次同余方程的解数和解法 素数模的同余方程 威尔逊定理。

高次方程及其解法求解程序编辑高次方程的根的求解，可以利用bairstow法，通过简单的matlab程序，求得方程的所有复根（实根和虚根）2定义编辑整式方程未知数次数最高项次数高于2次的方程，称为高次方程。

3一般形式编辑高次方程的一般形式为anx^n+an-1x^n-1+-------+a1x+a0=高次方程等式两边同时除以最高项系数，得：anx^n/an+an-1x^n-1/an+--------+a1x/an+a0/an=0所以高次方程一般形式又可写为x^n+bnx^n-1+-------b1x+b0=04其它相关编辑解法思想通过适当的方法，把高次方程化为次数较低的方程求解．根与系数按这个高次方程的形式x^n+bn-1x^n-1+-------b1x+b0=0，那么有所有根相加等于系数bn-1的相反数所有根两两相乘再相加等于系数bn-2所有根三三相乘再相加等于系数bn-3的相反数依次类推，直到所有根相乘，等于（-1）^nb0成果伽罗华（Galois，1811——1832），法国数学家。

伽罗华15岁进入巴黎有名公立中学学习，偏爱数学。

后来想进工科大学，两次落榜只进一所代等的预备学校，此时，他专攻五次方程代数解法。

第一年写了四篇文章，1828年，17岁的伽罗华写了《关于五次方程的代数解法问题》等两篇论文送交法国科学院，但被柯西（Cauchy,1789——1875）遗失，后来，他又把一篇文章送给傅利（Fourier，1768——1830）。

不久，傅利就去世了，也就不了了之。

1831年，伽罗华完成了《关于用根式解方程的可解性条件》一文，院士普阿松（Poisson，1781-1840）的审查意见却是“完全不能理解”，予以退回。

伽罗华不幸因决斗受重伤于1832年5月31日离世，时年不满21岁，在决斗前夜，他深知为女友决斗而死毫无意义，但又不甘示弱，当晚他精神高度紧张和极度不安，连呼“我没有时间了！”匆忙之中，把他关于方程论的发现草草写成几页说明寄给他的朋友，并附有如下一段话：“你可以公开地请求雅可比（Jacobi）或高斯，不是对于这些定理的真实性而是对于其重要性表示意见，将来我希望有人会发现这堆东西注释出来对于他们是有益的。

高次方程的解法高次方程是指次数大于等于2的方程，例如二次方程、三次方程、四次方程等。

解高次方程是数学中的基本技能之一，能够帮助我们研究各种实际问题。

本文将介绍几种解高次方程的方法，包括因式分解、配方法、提取公因式和根的公式等。

一、因式分解法当高次方程可因式分解时，我们可以通过因式分解的方式求解方程。

举个例子，考虑解二次方程x^2 - 5x + 6 = 0。

首先，我们观察方程中的常数项6，寻找其因数。

可以得知6的因数有1、2、3和6。

然后我们将这些因数带入方程，并观察是否能够满足等式。

不难发现，当将2和3带入方程时，等式成立。

因此，我们可以得出以下因式分解形式：(x - 2)(x - 3) = 0。

由因式分解的性质可知，当一个方程的乘积等于0时，其中一个因式等于0。

因此，我们可以得到两个解：x - 2 = 0 和 x - 3 = 0。

进一步求解可得x的值，即x = 2和x = 3。

因此，原方程的解为x = 2和x = 3。

二、配方法对于一些特殊的高次方程，我们可以通过配方法来求解。

配方法适用于二次方程以及一些特殊的三次方程，例如x^2 + bx + c = 0。

我们仍以二次方程为例进行讲解。

考虑解方程x^2 - 8x + 12 = 0。

首先，我们观察方程中的系数，将常数项12分解为两个数的乘积，这里可以分解为2和6。

然后我们观察方程中的一次项系数-8，将其写成-2和-6之和。

然后将方程重新写成完全平方的形式：(x - 2)(x - 6) = 0。

继续通过因式分解的性质可以得到x的两个解：x - 2 = 0 和 x - 6 = 0。

求解可得x = 2和x = 6。

因此，原方程的解为x = 2和x = 6。

三、提取公因式法当高次方程中存在公因式时，我们可以通过提取公因式的方式简化方程，并进一步求解。

举个例子，考虑解方程x^3 - 4x^2 + 4x = 0。

首先，我们观察方程中的每一项，可以发现每一项都含有x。

本科毕业论文题目：同余方程的解法学生姓名：学号：专业：数学与应用数学班级:指导教师：二〇一年四月摘要：本文论述了同余方程的基本概念及同余方程的一些基本性质与解法，主要对一次同余方程的解法进行了探讨，特别是对一次同余方程的欧拉定理算法，欧几里德算法等七种解法进行了比较与分析，并介绍了同余方程组、孙子定理、素数模的同余方程，模p 的同余方程的解法。

关键词：同余同余方程孙子定理Abstract：This paper mainly discusses the basic concepts of congruence equations and congruence equation some of the basic nature of solution,and highlights the Remainder Theorem,solution of the congruence equation,mod p congruence equation solution,congruence equation of primes mode solution,etc.Key words:Congruence Congruence equation Remainder Theorem目录引言 (1)1.同余与同余方程的基本性质 (2)1.1 同余的概念与基本性质 (2)1.2同余方程的概念与性质 (3)2.一次同余方程的解法 (4)2.1 ()a=的情况 (4), m 12.2 ()=≠的情况 (7),1a m d3.同余方程组的解法 (8)3.1简单同余方程组的解法 (8)3.2 孙子定理 (9)4.高次同余方程的的解法 (11)4.1素数模的同余方程 (11)4.2模pα的同余方程 (12)总结： (17)参考文献 (18)致谢： (19)引言对于同余方程的解法国内外的数学家们均对其做出了非常全面与细致的研究。

高次方程解法1.高次方程的定义整式方程未知数次数最高项次数高于2次的方程，称为高次方程。

2.高次方程的一般形式高次方程的一般形式为anx^n+an-1x^n-1+-------+a1x+a0=0等式两边同时除以最高项系数，得：anx^n/an+an-1x^n-1/an+--------+a1x/an+a0/an=0所以高次方程一般形式又可写为x^n+bnx^n-1+-------b1x+b0=03.高次方程解法思想通过适当的方法，把高次方程化为次数较低的方程求解4.高次方程根与系数的关系按这个高次方程的形式x^n+bn-1x^n-1+-------b1x+b0=0，那么有所有根相加等于系数bn-1的相反数所有根两两相乘再相加等于系数bn-2所有根三三相乘再相加等于系数bn-3的相反数依次类推，直到所有根相乘，等于(-1)^nb05.阿贝尔定理对于5次及以上的一元高次方程没有通用的代数解法和求根公式(即通过各项系数经过有限次四则运算和乘方和开方运算无法求解)，这称为阿贝尔定理。

换句话说，只有三次和四次的高次方程可解．下面介绍三次和四次方程的解法。

6.四次方程解法卡尔丹公式诞生后，卡尔丹的学生费拉里便发明了一元四次方程的求根公式。

【费拉里公式】一元四次方程aX＾4＋bX＾3＋cX＾2＋dX＋e=0，（a，b，c，d，e∈R，且a≠0）。

令a=1，则X＾4＋bX＾3＋cX＾2＋dX＋e=0，此方程是以下两个一元二次方程的解。

2X＾2＋(b＋M)X＋2(y＋N/M)=0；2X＾2＋(b—M)X＋2(y—N/M)=0。

其中M=√(8y＋b＾2—4c)；N=by—d，(M≠0)。

y是一元三次方程8y＾3—4cy＾2—(8e—2bd)y—e(b＾2—4c)—d＾2=0的任一实根。

7.三次方程解法一元三次方程的求根公式用通常的演绎思维是作不出来的，用类似解一元二次方程的求根公式的配方法只能将型如aX^3＋bX^2＋cX＋d=0的标准型一元三次方程形式化为X^3＋pX＋q=0的特殊型。

§4同余式1 基本概念及一次同余式定义 设()110nn n n f x a x a xa --=+++ ，其中()0,0,1,,i n a i n >= 是整数，又设0m >，则()()0mod f x m ≡ （1）叫做模m 的同余式.若()0mod n a m ≡，则n 叫做同余式（1）的次数. 如果0x 满足()()00mod ,f x m ≡则()0mod x x m ≡叫做同余式（1）的解.不同余的解指互不同余的解.当m 及n 都比较小时，可以用验算法求解同余式.如 例1 同余式()543222230mod 7x x x x x +++-+≡仅有解()1,5,6mod 7.x ≡例2 同余式()410mod16x -≡有8个解()1,3,5,7,9,11,13,15mod16x ≡例3 同余式()230mod 5x +≡无解。

定理 一次同余式()()0mod ,0mod ax m a m ≡≡ （2）有解的充要条件是(),.a m b若（2）有解，则它的解数为(),d a m =. 以及当同余式（2）有解时，若0x 是满足（2）的一个整数，则它的(),d a m =个解是()0mod ,0,1,,1mx x k m k d d≡+=- （3） 证 易知同余式（2）有解的充要条件是不定方程ax my b =+ （4）有解. 而不定方程（4）有解的充要条件为()(),,.a m a m b =-当同余式（2）有解时，若0x 是满足（2）的一个整数，则()0mod ,0,1,, 1.m a x k b m k d d ⎛⎫+≡=- ⎪⎝⎭下证0,0,1,,1mx k k d d +=- 对模m 两两部同余. 设 ()00mod ,01,1m mx k x k m k d k d d d ''+≡+≤≤-≤≤-则()mod ,mod ,.m m m k k d k k d k k d d d ⎛⎫'''≡≡= ⎪⎝⎭再证满足（2）的任意一个整数1x 都会与某一个()001mx k k d d+≤≤-对模m 同余. 由()()01mod ,mod ax b m ax b m ≡≡得()101010mod ,mod ,.a a m m ax ax m x x x x d d d d ⎛⎫⎛⎫≡≡≡ ⎪ ⎪⎝⎭⎝⎭故存在整数t 使得10.mx x t d=+由带余除法，存在整数,q k 使得 ,0 1.t dq k k d =+≤≤-于是()()100mod .m mx x dq k x k m d d=++≡+故（2）有解时，它的解数为(),d a m =. 以及若0x 是满足（2）的一个整数，则它的(),a m 个解是()0mod ,0,1,,1mx x k m k d d≡+=- (5) 例1求同余式 ()912m o d 15x ≡ （6）的解. 解 因为()9,15 3.=又因312,故同余式（6）有解，且有三个解.先解()5mod 43≡x , 得().5mod 3≡x 故同余式（6）的三个解为()158mod15,0,1,2.3x k k ≡+= 即 ()3,8,13m o d 15.x ≡ 例2 求同余式 ()6483mod105x ≡ （7）的解. 解 ()831,1105,64= ,同余式有一个解. 将同余式表为21051921916152161054716476418864105836483+≡≡≡+≡≡≡+≡≡x ().105mod 622124≡≡例3 解同余式 325x ≡ 20 (mod 161) 解 ()1161,325= 同余式有一个解, 同余式即是3x ≡ 20 (mod 161) 即.161203y x +=解同余式 161y ≡ -20 (mod 3)， 即2y ≡ 1 (mod 3)， 得到y ≡ 2 (mod 3)，因此同余式的解是x ≡3161220⋅+= 114 (mod 161). 例4 设(a , m ) = 1，并且有整数δ > 0使得 a δ ≡ 1 (mod m )， 则同余式(2)的解是x ≡ ba δ - 1 (mod m ). 解 直接验证即可.注：由例4及Euler 定理可知，若(a , m ) = 1，则x ≡ ba ϕ(m ) - 1 (mod m ) 总是同余式(2)的解.注：本例使用的是最基本的解同余方程的方法，一般说来，它的计算量太大，不实用. 例5 解同余方程组⎩⎨⎧≡-≡+)7(mod 232)7(mod 153y x y x (8) 解 将(8)的前一式乘以2后一式乘以3再相减得到19y ≡ -4 (mod 7)，5y ≡ -4 (mod 7)， y ≡ 2 (mod 7).再代入(8)的前一式得到3x + 10 ≡ 1 (mod 7)，x ≡ 4 (mod 7)即同余方程组(8)的解是x ≡ 4，y ≡ 2 (mod 7).例6 设a 1，a 2是整数，m 1，m 2是正整数，证明：同余方程组⎩⎨⎧≡≡)(mod )(mod 2211m a x m a x (9) 有解的充要条件是a 1 ≡ a 2 (mod (m 1, m 2)). (10)若有解，则对模[m 1, m 2]是唯一的，即若x 1与x 2都是同余方程组(9)的解，则x 1 ≡ x 2 (mod [m 1, m 2]) (11)解 必要性是显然的.下面证明充分性.若式(10)成立，由定理2，同余方程m 2y ≡ a 1 - a 2 (mod m 1)有解y ≡ y 0 (mod m 1)，记x 0 = a 2 + m 2y 0，则x 0 ≡ a 2 (mod m 2)并且x 0 = a 2 + m 2y 0 ≡ a 2 + a 1 - a 2 ≡ a 1 (mod m 1)，因此x 0是同余方程组的解。

第4章原根和指数原根和指数高次同余方程(mod)k≡x a n4.1 原根设1n ≥，(,)1a n =，是否有正整数d 使得1(mod )d a n ≡？ 定义4.1.1 设1n ≥，(,)1a n =，使得1(mod )da n ≡成立的最小正整数d ，称为a 对模n 的阶，记作()n a δ。

定理 4.1.1 设n 为正整数，(,)1a n =，若1(mod )d a n ≡，则()|n a d δ。

推论4.1.1设n 为正整数，(,)1a n =，则有()|()n a n δϕ。

定义4.1.2 当()()n a n δϕ=时，称a 是模n 的原根。

例1 10n =，取模10的一个缩系{1,3,7,9}， 因为111(mod10)≡；23439(mod10),37(mod10),31(mod10)≡≡≡；279(mod10),≡373(mod10),≡471(mod10)≡；291(mod10)≡; 所以10101010(1)1,(3)4,(7)4,(9)2δδδδ====，它们都是(10)4ϕ=的因子，且3和7均是模10的原根。

例2 8n =，取模8的一个缩系1,3,5,7， 因为122211(mod8),31(mod8),51(mod8),71(mod8),≡≡≡≡所以8888(1)1,(3)2,(5)2,(7)2δδδδ====，而(8)4ϕ=，故而模8没有原根。

定理4.1.2 (1) 若(mod )a b n ≡，(,)1a n =，则()()n n a b δδ=。

(2) 若(,)1a n =，(mod )k l a a n ≡，则(mod ())n k l a δ≡。

(3) 若(,)1a n =，则()1011,,,n a a a a δ−=L 这()n a δ个数模n 两两不同余，特别当a 是模n 的原根时，这()()n a n δϕ=个数是模n 的一组缩系。

(4) 设1a −是a 模n 的逆，则1()()n n a a δδ−=。

高次方程及解法 江苏省通州高级中学 徐嘉伟 一般地，我们把次数大于2的整式方程，叫做高次方程。

由两个或两个以上高次方程组成的方程组，叫做高次方程组。

对于一元五次以上的高次方程，是不能用简单的算术方法来求解的。

对于一元五次以下的高次方程，也只能对其中的一些特殊形式的方程，采用“±1判根法”、“常数项约数法”、“倒数方程求根法”、“双二次方程及推广形式求解法”等方法，将一元五次以下的高次方程消元、换元、降次，转化成一次或二次方程求解。

一、±1判根法在一个一元高次方程中，如果各项系数之和等于零，则1是方程的根；如果偶次项系数之和等于奇次项系数之和，则-1是方程的根。

求出方程的±1的根后，将原高次方程用长除法或因式分解法分别除以（x-1）或者（x+1）,降低方程次数后依次求根。

“±1判根法”是解一元高次方程最简捷、最快速的重要方法，一定要熟练掌握运用。

例1解方程x4+2x3-9x2-2x+8=0解：观察方程,因为各项系数之和为:1+2-9-2+8=0(注意:一定把常数项算在偶数项系数当中),根据歌诀“系和零,+1根”,即原方程中可分解出因式(x-1),Θ(x4+2x3-9x2-2x+8)÷(x-1)= x3+3x2-6x-8观察方程x3+3x2-6x-8=0，偶次项系数之和为：3-8=-5；奇次项系数之和为：1-6=-5，根据歌诀“偶等奇，根-1”，即方程中含有因式（x+1），∴（x3+3x2-6x-8）÷(x+1)=x2+2x-8，对一元二次方程x2+2x-8=0有（x+4）（x-2）=0, ∴原高次方程x4+2x3-9x2-2x+8=0可分解因式为：(x-1) (x+1)(x-2)(x+4)=0,即:当(x-1)=0时,有x1=1;当(x+1)＝０时，有x2= -1;当(x-2) =0时，有x3=2; 当(x+4)=0时，有x4=-4点拨提醒：在运用“±1判根法”解高次方程时，一定注意把“常数项”作为“偶次项”系数计算。