下载文档原格式
初等数论（1）----数的整除初等数论又称初等整数论，它的研究对象是整数集。
整数是小学就接触的一类数，但是关于数论的问题却是最难解决的。
1、整数的离散性：任何两个整数,x y 之间的距离至少为1，因此有不等式1x y x y <⇔+≤。
例如：（1）若222912842440a ab b bc c c -+-+-+=，求a b c ++的值.（2）求整数,,a b c ，使它们满足不等式222332a b c ab b c +++<++.作比较。
2、整数的奇偶性：将全体整数分为两类，凡是2的倍数的数称为偶数，否则称为奇数.因此，任一偶数可表为2m （m ∈Z ），任一奇数可表为2m+1或2m －1的形式.关于奇数和偶数，有下面的性质：（1）奇数不会同时是偶数；两个连续整数中必是一个奇数一个偶数；（2）奇数个奇数和是奇数；偶数个奇数的和是偶数；任意多个偶数的和是偶数； （3）奇数±奇数=偶数；偶数±偶数=偶数； 奇数±偶数=奇数；偶数×偶数=偶数； 奇数×偶数=偶数；奇数×奇数=奇数；（4）两个整数的和与这两个整数的差有相同的奇偶性； （5）奇数的平方都可表为81m +形式，偶数的平方都可表为8m 或84m +的形式（m ∈Z ）. （6）任意两个整数的平方和被4除余数不可能是3. （7）任意两个整数的平方差被4除余数不可能是2.以上性质简单明了，解题时如果能巧妙应用，常常可以出奇制胜.例如： 1．（1）已知c b a ,,是整数，c b a ++是奇数，判断c b a -+，c b a +-，c b a ++-的奇偶性，说明理由。
（2）你能找到三个整数c b a ,,，使得关系式()()()()2010a b c a b c a b c b c a ++-++-+-=成立吗？如果能找到，请举一例，如果找不到，请说明理由.2、是否存在整数,m n ，满足222010m n +=?3、设1,2,3,,9的任一排列为1239,,,,a a a a ，求证：129(1)(2)(9)a a a ---是一个偶数. 类题：（1906，匈牙利）假设12,,,n a a a 是1,2,,n 的某种排列，证明：如果n 是奇数，则乘积()()()1212n a a a n ---是偶数.解法1 （反证法）假设()()()1212n a a a n ---为奇数，则i a i -均为奇数，奇数个奇数的和还是奇数奇数=()()()1212n a a a n -+-++-()()12120n a a a n =+++-+++=，这与“奇数≠偶数”矛盾. 所以()()()1212n a a a n ---是偶数.评析 这个解法说明()()()1212n a a a n ---不为偶数是不行的，体现了整体处理的优点，但掩盖了“乘积”为偶数的原因. 解法2 （反证法）假设()()()1212n a a a n ---为奇数，则i a i -均为奇数，i a 与i 的奇偶性相反，{}1,2,,n 中奇数与偶数一样多，n 为偶数但已知条件n 为奇数，矛盾. 所以()()()1212n a a a n ---是偶数.评析 这个解法揭示了()()()1212n a a a n ---为偶数的原因是“n 为奇数”.那么为什么“n 为奇数”时“乘积”就为偶数呢？解法3 121,2,,,,,,n n a a a 中有1n +个奇数，放到n 个括号，必有两个奇数在同一个括号，这两个奇数的差为偶数，得()()()1212n a a a n ---为偶数.例4-1（1986，英国）设127,,,a a a 是整数，127,,,b b b 是它们的一个排列，证明()()()112277a b a b a b ---是偶数.例4-2 π的前24位数字为 3.14159265358979323846264π=，记1224,,,a a a 为该24个数字的任一排列，求证()()()12342324a a a a a a ---必为偶数.4、有n 个数12,,,n x x x ，它们中的每一个数或者为1，或者为1-，如果1234110n n n x x x x x x x x -++++=，求证：n 是4的倍数。
初等数论总复习题及知识点总结最后，给大家提一点数论的学习方法，即一定不能忽略习题的作用，通过做习题来理解数论的方法和技巧，华罗庚教授曾经说过如果学习数论时只注意到它的内容而忽略习题的作用，则相当于只身来到宝库而空手返回而异。
数论有丰富的知识和悠久的历史，作为数论的学习者，应该懂得一点数论的常识，为此在辅导材料的最后给大家介绍数论中著名的“哥德巴赫猜想”和费马大定理的阅读材料。
初等数论自学安排第一章：整数的可除性（6学时）自学18学时整除的定义、带余数除法最大公因数和辗转相除法整除的进一步性质和最小公倍数素数、算术基本定理[x]和{x}的性质及其在数论中的应用习题要求：2，3 ；：4 ；：1；：1，2，5；：1。
第二章：不定方程（4学时）自学12学时二元一次不定方程多元一次不定方程勾股数费尔马大定理。
习题要求：1，2，4；：2，3。
第三章：同余（4学时）自学12学时同余的定义、性质剩余类和完全剩余系欧拉函数、简化剩余系欧拉定理、费尔马小定理及在循环小数中的应用习题要求：2，6；：1；：2，3；1，2。
第四章：同余式（方程）（4学时）自学12学时同余方程概念孙子定理高次同余方程的解数和解法素数模的同余方程威尔逊定理。
习题要求：1；：1，2；：1，2。
第五章：二次同余式和平方剩余（4学时）自学12学时二次同余式单素数的平方剩余与平方非剩余勒让德符号二次互反律雅可比符号、素数模同余方程的解法习题要求：2；：1，2，3；：1，2；：2；：1。
第一章：原根与指标（2学时）自学8学时指数的定义及基本性质原根存在的条件指标及n次乘余模2及合数模指标组、特征函数习题要求：3。
第一章整除一、主要内容整除的定义、带余除法定理、余数、最大公因数、最小公倍数、辗转相除法、互素、两两互素、素数、合数、算术基本定理、Eratosthesen筛法、[x]和{x}的性质、n！的标准分解式。
二、基本要求通过本章的学习，能了解引进整除概念的意义，熟练掌握整除整除的定义以及它的基本性质，并能应用这些性质，了解解决整除问题的若干方法，熟练掌握本章中二个著名的定理：带余除法定理和算术基本定理。
初等数论基本思想方法总结初等数论是研究整数性质及其关系的数学分支，它包括了数的整除性质、最大公因数、素数分解等基本概念和理论。
初等数论的基本思想方法总结如下：1. 数的分类：在初等数论中，数的分类是非常重要的一步。
我们把整数分为偶数和奇数、正整数和负整数、完全平方数和非完全平方数等等。
这样的分类有助于我们更好地理解和描述数的性质。
2. 递归思想：初等数论中经常使用递归思想。
例如，整数的定义是基于自然数的递归定义。
在证明一些性质的时候，我们也可以使用数的递归性质来进行推导。
递归思想在解决问题时，常常能够将复杂的问题简化为简单的子问题。
3. 数的整除性质：整除是初等数论最基本的概念之一。
在初等数论中，我们要研究一个数能否被另一个数整除、两个数的最大公因数等问题。
对于整除性质的研究，我们常常使用带余除法、最大公因数等概念和定理。
4. 素数和合数：素数和合数是初等数论中重要的概念。
我们称大于1且只能被1和它本身整除的数为素数，否则我们称之为合数。
素数的性质在初等数论中有着重要的地位，素数分解定理将任意一个正整数表示为若干个素数的乘积，具有重要的理论和应用价值。
5. 辗转相除法：辗转相除法是初等数论中常用的算法之一。
它用于求两个数的最大公因数，通过不断地进行除法运算，将两个整数的最大公因数转化为较小整数的最大公因数，直到其中一个数为0为止。
6. 数的因子分解：在初等数论中，我们常常需要将一个数分解为几个素数和幂的乘积。
这种分解是数的因子分解，可以通过素数分解定理和辗转相除法来实现。
7. 同余：同余是初等数论中重要的概念和方法之一。
两个整数除以一个正整数所得的余数（都是非负整数）相等，我们就说这两个数对于这个正整数是同余的。
同余关系可以用来刻画整数的性质和关系，也可以用来解决一些问题。
8. 数的循环节性：在初等数论中，很多整数序列会出现循环节。
例如，10进制小数中的循环节、数的幂的个位数循环节等等。
这样的循环节性质可以通过数的除法和模运算来进行研究和验证。
高中数学：“初等数论”一、知识点概述初等数论是研究自然数的性质及其相互关系的一门数学学科，其研究对象是自然数和它们的运算。
初等数论主要研究质数、公因数和最大公因数、同余、数的分解、勒让德符号、二次剩余等数论基础知识。
二、重点概念解释1. 质数：大于1的自然数，除1和它本身外，不能被其它自然数整除的数字称为质数。
2. 素数：素数是指只有1和它本身两个约数的数。
3. 最大公因数：指两个或两个以上整数共有约数中，最大的一个。
4. 同余：对于任意整数a、b、n（n≠0），若n|(a-b)，则称a与b在模n条件下同余，记作a≡b(mod n)。
5. 勒让德符号：勒让德符号（Legendre Symbol）是一种特殊的符号，用来判断一个整数是否是二次剩余，即其是否满足某些特殊性质。
三、典型例题分析例题1：求最大公因数gcd(100, 80)。
答案：首先列出100=2^2×5^2，80=2^4×5，公共因子为2^2×5，即gcd(100,80)=20。
例题2：判断71^25与81在模10下是否同余。
答案：将71=7×10+1，用费马小定理得7^4≡1(mod 10)，于是71^25≡(7×10+1)^25≡7^25≡7(mod 10)。
又81≡1(mod 10)，因此不同余。
例题3：判断21与31在模5下是否有逆元。
答案：首先求21与31分别除以5的余数为1和1，因为1和5互素，所以1有逆元，然后判断31在模5下是否有逆元：31除以5余1，31与5不互素，因此31在模5下没有逆元。
例题4：求解同余方程3x≡4(mod 5)。
答案：gcd(3,5)=1，因此同余方程有解。
将方程两边乘以3的逆元2（即2×3≡1(mod 5)）得到6x≡8(mod 5)，即x≡3(mod 5)。
因此，同余方程的解为x≡3(mod 5)。
例题5：对于勒让德符号(a/p)，当p为素数，a为整数时，有以下性质：i. (a/p)=0当且仅当a≡0(modp)。
初等数论的性质与定理总结初等数论是数论中的一个基础分支，研究整数的性质和整数运算规律。
本文将总结初等数论中的一些重要性质与定理。
一、整数的整除性质1. 整数的除法基本性质：对于任意整数a、b和非零整数c，存在唯一的整数q使得a = bq + c。
2. 整除关系的传递性：如果a能整除b，且b能整除c，则a能整除c。
3. 整除关系的辗转相除法：对于任意整数a和非零整数b，存在唯一的整数q和r使得a = bq + r（其中0 ≤ r < |b|）。
二、质数与合数1. 质数的定义：质数是指大于1且只能被1和自身整除的整数。
例如，2、3、5、7等都是质数。
2. 质因数分解定理：每个大于1的整数都可以唯一地表示为若干个质数的乘积。
3. 最大公约数与最小公倍数的性质：对于任意整数a和b，记a和b 的最大公约数为gcd(a, b)，最小公倍数为lcm(a, b)，则有以下性质： - gcd(a, b) = gcd(b, a)- gcd(a, 0) = |a|- lcm(a, b) = |ab| / gcd(a, b)三、模运算与同余1. 模运算的基本性质：对于任意整数a、b和正整数n，有以下性质：- (a + b) mod n = (a mod n + b mod n) mod n- (a - b) mod n = (a mod n - b mod n) mod n- (a * b) mod n = (a mod n * b mod n) mod n2. 同余关系的性质：对于任意整数a、b和正整数n，如果a与b模n同余（记作a ≡ b (mod n)），则有以下性质：- a + c ≡ b + c (mod n)- ac ≡ bc (mod n)- 如果a ≡ b (mod n)，则a^k ≡ b^k (mod n)对于任意正整数k四、费马小定理与欧拉定理1. 费马小定理：如果p是质数，a是任意正整数且p不整除a，则有a^(p-1) ≡ 1 (mod p)。
初等数论知识点整理 1. 整数的基本性质：
- 整数的定义与整数集的基本运算
- 整数的大小与比较
- 整数的不同表示形式（十进制、二进制、八进制等） 2. 整除与约数：
- 整除的定义与性质
- 素数的定义与判定方法
- 约数的定义与性质
- 最大公约数与最小公倍数的概念与计算方法
3. 同余与模运算：
- 同余的定义与性质
- 同余的基本运算性质
- 模运算的基本性质
- 剩余类和完全剩余系的概念与性质
4. 质数与素数：
- 质数与素数的定义
- 质数与素数的性质和特性
- 素数的测试方法与算法
- 质因数分解的方法与应用
5. 数论基本定理：
- 唯一分解定理（素因数分解定理）
- 辗转相除法与欧几里得算法
- 欧拉函数与欧拉定理
- 费马小定理与扩展欧几里得算法
6. 数论问题的应用：
- 同余方程与线性同余方程
- 不定方程的整数解与应用
- 素数分布与素数定理
- 模重复性与周期性问题
注意：本整理的所有内容仅供参考，请勿将其作为官方教材或其他正式场合使用。
初等数论知识点总结初等数论是数论中的一个分支，它主要研究自然数的整除性质以及其它基本性质。
初等数论主要包括素数与合数、整数表示、整数方程、模运算、同余方程、数乘次幂循环节等内容。
下面将对初等数论的关键知识点进行总结。
1.素数与合数：素数（质数）是只能被1和自身整除的自然数，合数是除了1和自身以外还能被其它数整除的自然数。
质数有无穷多个，这个结论由欧几里得证明。
常见的质数有2、3、5、7等。
2.素因子分解：任何一个自然数都可以唯一分解成若干个素数的乘积形式，这个分解过程称为素因子分解。
例如，24可以分解为2^3*3，其中2和3是24的素因子。
3.最大公约数与最小公倍数：最大公约数（GCD）是指两个或多个数中最大的能够整除所有这些数的自然数，最小公倍数（LCM）是指两个或多个数中最小的能够被这些数整除的自然数。
GCD可以通过欧几里得算法进行计算，而LCM可以通过两个数的乘积除以它们的GCD得到。
4.模运算与同余方程：模运算是将一个数除以另一个数所得到的余数，同余方程是指具有相同余数的整数关系。
例如，如果a除以n与b除以n得到相同的余数，即a≡b (mod n)，则称a与b在模n下是同余的。
5.素数定理与欧拉定理：素数定理是指当自然数x趋于无穷大时，小于等于x的素数的数量约等于x / ln(x)，其中ln(x)是自然对数。
欧拉定理是指当正整数a与自然数n互质时，a^(φ(n)) ≡ 1 (mod n)，其中φ(n)是小于n且与n互质的自然数的个数。
6.立方与四方数：立方数是指一个数的立方，四方数是指一个数可以表示为四个整数的平方和。
高斯数学说是指四方数的性质，它由高斯证明，表示为四个整数的平方和的非负整数解的个数等于该数的除以8的余数。
7.费马小定理与小费马定理：费马小定理是费马定理的一个特殊情况，它表明如果p是一个素数，a是一个与p互质的整数，那么a^(p-1) ≡ 1 (mod p)。
小费马定理是费马小定理的推广，它表明如果a是一个整数，m是一个大于1的自然数，且a与m互质，那么a^φ(m) ≡ 1 (mod m)，其中φ(m)是小于m且与m 互质的自然数的个数。
初等数学知识点汇总一、绝对值1、非负性：即|a| ≥ 0，任何实数a 的绝对值非负。
归纳：所有非负性的变量（1） 正的偶数次方（根式） 0,,,,412142≥a a a a Λ（2） 负的偶数次方（根式） 112424,,,,0a a a a---->L（3） 指数函数 a x(a > 0且a ≠1)>0考点：若干个具有非负性质的数之和等于零时，则每个非负数必然为零。
2、三角不等式，即|a| - |b| ≤ |a + b| ≤ |a| + |b| 左边等号成立的条件：ab ≤ 0且|a| ≥ |b|右边等号成立的条件：ab ≥ 03、 要求会画绝对值图像 二、比和比例1、%(1%)ap a p −−−→+原值增长率现值 %)1(%p a p a-−−→−现值下降率原值 %%%%p p p p ⋅=⇔=-⇔乙甲，甲是乙的乙乙甲注意：甲比乙大 2、 合分比定理：d b ca m mdb mc ad c b a ±±=±±==1等比定理：.a c e a c e a b d f b d f b++==⇒=++ 3、增减性1>b a b a m b m a <++ (m>0) , 01a b << ba mb m a >++ (m>0) 4、 注意本部分的应用题（见专题讲义） 三、平均值1、当n x x x ，⋯⋯,,21为n 个正数时，它们的算术平均值不小于它们的几何平均值，即),1 0( ·2121n i x x x x nx x x i nn n ，＝＞＋＋＋⋯⋯≥⋯当且仅当时，等号成立＝n x x x ⋯⋯==21。
2、 2ab b a ≥＋⎪⎩⎪⎨⎧>>等号能成立另一端是常数，00b a3、2(0)a bab ab b a≥>＋ ，同号 4、n 个正数的算术平均值与几何平均值相等时，则这n 个正数相等，且等于算术平均值。
《初等数论》总结姓名 xxx学号 xxxxxxxx院系 xxxxxxxxxxxxxxx专业 xxxxxxxxxxxxxxx个人感想初等数论是一门古老的学科，它对于数的性质以及方程整数的解做了深入的研究，是对中等数学数的理论的继续和提高。
有时候上课听老师讲解一些例题，觉得比较简单，结果便是懂非懂地草草了之，但是过段时间做老师留下的一些相似的课后练习时，又毫无头绪，无从下手。
这就是上课的时候没做到全神贯注地去听，所以课下的时间尤为重要，一定做好复习巩固的工作。
老师讲课的方法也十分好，每次上课都会花二十分钟到半个小时来对上节课的知识帮助我们进行回顾，我想很多同学都喜欢并适合这种教学方式。
知识点总结第一章 整数的可除性1. 定义：设b a ,是给定的数，0≠b ，若存在整数c ，使得bc a =则称b 整除a ，记作a b |，并称b 是a 的一个约数，称a 是b 的一个倍数，如果不存在上述c ，则称b 不能整除a 2性质：(1)若c b |且a c |，则a b |(传递性质)；(2)若a b |且c b |，则)(|c a b ±即为某一整数倍数的整数之集关于加、减运算封闭。
若反复运用这一性质，易知a b |及c b |，则对于任意的整数v u ,有)(|cv au b ±。
更一般，若n a a a ,,,21Λ都是b 的倍数，则)(|21n a a a b +++Λ。
或着i b a |，则∑=ni ii b c a 1|其中n i Z c i ,,2,1,Λ=∈；(3)若a b |，则或者0=a ，或者||||b a ≥，因此若a b |且b a |，则b a ±=； (4)b a ,互质，若c b c a |,|，则c ab |；(5)p 是质数，若n a a a p Λ21|，则p 能整除n a a a ,,,21Λ中的某一个；特别地，若p 是质数，若n a p |，则a p |；(6)(带余数除法)设b a ,为整数，0>b ，则存在整数q 和r ，使得r bq a +=，其中b r <≤0，并且q 和r 由上述条件唯一确定；整数q 被称为a 被b 除得的(不完全)商，数r 称为a 被b 除得的余数。
注意：r 共有b 种可能的取值：0,1，……，1-b 。
若0=r ，即为a 被b 整除的情形；易知，带余除法中的商实际上为⎥⎦⎤⎢⎣⎡b a （不超过b a 的最大整数），而带余除法的核心是关于余数r 的不等式：b r <≤0。
证明a b |的基本手法是将a 分解为b 与一个整数之积，在较为初级的问题中，这种数的分解常通过在一些代数式的分解中取特殊值而产生若n 是正整数，则))((1221----++++-=-n n n n n n y xy y x x y x y x Λ；若n 是正奇数，则))((1221----+-+-+=+n n n n n n y xy y x x y x y x Λ；（在上式中用y -代y ）(7)如果在等式∑∑===mk k ni i b a 11中取去某一项外，其余各项均为c 的倍数，则这一项也是c 的倍数；(8)n 个连续整数中，有且只有一个是n 的倍数；(9)任何n 个连续的整数之积一定是n!的倍数，特别地，三个连续的正整数之积能被6整除；第二章 不定方程1. 定义：二元一次不定方程的一般形式是ax +by = c ，其中a ,b ,c 是整数2. 定理：(1) 不定方程有整数解的充要条件为 (a,b) | c. (2) 设是方程的一组解，则不定方程有无穷解，其一切解可表示成⎩⎨⎧+=-=ta y y tb x x 1010 Λ,2,1,0±±=t其中),(,),(11b a b b b a a a ==3. 不定方程的解法：（1）观察法：当a,b 的绝对值较小时可直接观察不定方程的一组特解，然后用⎩⎨⎧+=-=t a y y tb x x 1010得到其所有解（2）公式法：当a,b 的绝对值较小时，可用公式211021110,,1,0,,1----+===+===k k k k k k k k P Q q Q Q Q P P q P q P P 得到特解n n n n P y Q x )1(,)1(010-=-=-，然后用公式写出一切解。
i q 为a,b 作辗转相除时不完全商（3）整数分离法：当a,b 中系数不同时，用绝对值较小的系数后的变量表示另一个变量，通过变量替换得到一个新的不定方程。
如此反复，直到一个参数的系数为1，而得到不定方程的解。
（4）化为同余方程|)|(mod b c ax ≡ 4.多元一次不定方程（1）定义：形如)2(2211≥=++n c x a x a x a n n Λ的不定方程多元一次不定方程（2）定理：)2(2211≥=++n c x a x a x a n n Λ有解的充要条件是（3）解法：设n n n d a d d a d d a a ===-),(,),(,),(1332221Λ，则)2(2211≥=++n c x a x a x a n n Λ等价于方程组cx a t d t d x a t d t d x a x a n n n n =+=+=+--11333322222211,,ΛΛ先解最后一个方程的解，得n n x t ,1-然后把其代入倒数第二个方程求得一切解，如此向上重复进行，求得所有方程的解 5．勾股数定义：一般地称x 2+y 2=z 2的正整数解为勾股数 定理：在条件x>0，y>0，z>0，（x ，y ）=1，2∣x 的条件下x 2+y 2=z 2的通解公式为 x=2ab ，y=a 2-b 2，z 2=a 2+b 2，a>b>0 , (a ,b)=1，a ,b 一奇一偶第三章 同余1.定义：下列同余述是等价的 (1) a ≡ b (mod m )；(2) 存在整数q ，使得a = b + qm ；(3) 存在整数q 1，q 2，使得a = q 1m + r ，b = q 2m + r ，0 ≤ r < m 2.性质：(1) (自反性) a ≡ a (mod m )；(2) (对称性) a ≡ b (mod m ) ⇒ b ≡ a (mod m );(3) (传递性) a ≡ b ，b ≡ c (mod m ) ⇒ a ≡ c (mod m )。
(4)设a ，b ，c ，d 是整数，并且a ≡ b (mod m )，c ≡ d (mod m )， 则 (ⅰ) a + c ≡ b + d (mod m ) (ⅱ) ac ≡ bd (mod m )(5)设a i ，b i （0 ≤ i ≤ n ）以及x ，y 都是整数，并且x ≡ y (mod m )，a i ≡ b i (mod m )，0 ≤ i ≤ n ，则).(mod 0m y b x a ni i i niii ∑∑==≡3. 设m 是一个给定的正整数，()0,1,,1r K r m =-L 表示所有形如()0,1,2,qm r q +=±±L 的整数组成的集合，则称011,,,m K K K -L 为模m 的剩余类 （1）设0110,,,,m m K K K ->L 是模m 的剩余类，则（ⅰ）每一整数必包含于某一个类里，而且只能包含于一个类里； （ⅱ）两个整数,x y 属于同一类的充分必要条件是()mod .x y m ≡4. 在模m 的剩余类011,,,m K K K -L 中，各取一数,0,1,,1j j a C j m ∈=-L ，此m 个数011,,,m a a a -L 称为模m 的一个完全剩余系（m 个整数作成模m 的一个完全剩余系的充分必要条件是这m 个整数两两对模m 不同余）（1）设m 是一个正整数，,a b 都为整数，(),1a m =，若x 通过模m 的一个完全剩余系，则ax b +也通过模m 的一个完全剩余系（2）设()12120,0,,1m m m m >>=，而12,x x 分别通过模12,m m 的一个完全剩余系，则2112m x m x +通过模12m m 的一个完全剩余系5. 欧拉函数：φ(m )是1, 2, …, m 中与m 互质的个数，称为欧拉函数（1）欧拉函数值的计算公式：若m ＝p 1α1p 2α2…p n αn , 则φ(m )＝m (1－1p 1)(1－1p 2)…(1－1p n )，如30＝2·3·5，则.8)511)(311)(211(30)30(=---=ϕ（2）若p 为素数，则1()1,()(1),k k p p p p p ϕϕ-=-=-若p 为合数，则()2,p p ϕ≤-（3）不超过n 且与n 互质的所有正整数的和为1()2n n ϕ（4）若(,)1()()(),a b ab a b ϕϕϕ=⇒= 若()()a b a b ϕϕ⇒（5）设d 为n 的正约数，则不大于n 且与n 有最大公因数d 的正整数个数为()ndϕ，同时()()d nd nn d n dϕϕ==∑∑6.欧拉定理：若(a , m )＝1，则a φ(m )≡1(mod m )7.费马定理：若p 是素数，则a p ≡a (mod p ) 若另上条件(a ，p )＝1，则a p −1≡1(mod p )第四章 同余方程1.定义：设01)(a x a x a x f n n ++=Λ，+∈∈Z m Z a i ,，则)(mod 0)(m x f ≡叫做模m 的同余方程。
若)(mod 0m a n ≡，则称n 为同余方程的次数。
若)(mod 0)(m c f ≡，则)(mod m c x ≡称为同余式的解；模m 的一个完全剩余系中满足同余方程的个数称为满足同余方程的解数 注：对模m 互相同余的解是同一个解2.一次同余方程的一般形式为ax≡b(mod m)，)(mod 0/m a ≡，有解的充要条件是(a,m)|b,若有解则有d=(a,m)个关于模m 的解3.一次同余方程ax≡b(m od m)的解法 （1）化为不定方程ax+my=b（2）利用欧拉定理，若(a,m)=1,则有ax≡b(mod m),两边同乘1)(-m aϕ则有)(mod 1)()(m ba x a m m -≡ϕϕ，因为)(mod 1)(m a m ≡ϕ，因此)(mod 1)(m ba x m -≡ϕ （3）用形式分数当（a ，m ）=1时，若ab ≡1(modm)，则记b a1≡(modm)称为形式分数，根据定义和记号，)(mod 1m c a ac ≡有性质(a)Z t t m mt a mt c a c ∈++≡2121,),(mod (b) （d ，m ）=1，且11,dc c da a ==，则)(mod 11m aca c ≡利用形式分数的性质把分母变成1，从而求出一次同余式的解4.一次同余方程组的解法定义:如下(*)称为一次同余方程组 x≡b 1(mod m 1) x≡b 2(mod m 2)…… （*） x≡b k (mod m k )有解判定定理：同余方程组（*）有解的充要条件是j i b b m m j i j i ≠∀-,|),( 5.孙子定理：设k m m m Λ,,21，两两互素，则同余式(*)组的解为)(mod ,2,221,11i k k k m b M M b M M b M M x Λ++≡k m m m m Λ21=注：若给出的同余方程组不是标准形式，必须注意化为标准形式，同时我们得到的有解的判别定理及求解方法都是在这一标准形式得到的 6.高次同余方程（1）定义：次数大于1的同余方程称为高次同余方程)(mod 0)(m x f ≡，01)(a x a x a x f n n ++=Λ对一般模的高次同余方程我们要通过“小模”和“降次”的方法来得到一般模的高次同余方程的解（2）小模：即把一般模高次同等方程转化为一系列模两两互素的高次同余方程组注：因为k k p p p m αααΛ2121=，所以)(mod 0)(m x f ≡等价于同余方程组 k i p x f i i Λ2,1),(mod 0)(=≡α，即原方程可化为解)(mod 0)(αp x f ≡，而若x 是)(mod 0)(αp x f ≡的解，所以理论上只要解素数模)(mod 0)(p x f ≡同余方程即可（3）降次：设p 是素数，01)(a x a x a x f n n ++=Λ，是整系数多项式，设1x 是)(mod 0)(1-≡αp x f 的一个解，则有○1 )(mod 0)(1,p x f ≡则存在整数t 使得t p x x 11-+=α是)(mod 0)(αp x f ≡的解○2 )(mod 0)(1,p x f ≡且)(mod 0)(1αp x f ≡，则t p x x 11-+=α，当t=0，1，2，……P -1时，都是)(mod 0)(αp x f ≡的解 7.素数模同余方程)(mod 0)(p x f ≡ （*）定理：同余方程（*）或者有P 个解，或者与一个次数不超过p-1次的素数模同余方程等价（注意：同余方程（*）的解数不超过它的次数）（1）p 是素数，对任意的x 有)))(mod 1(()2)(1(11p p x x x x p ----≡--Λ （2）p 是素数，则有)(mod 01)!1(p p ≡+-（威尔逊定理）（3）,p n ≤同余方程（*）有n 个解的充要条件是存在q （x ）和r （x ），使得)()()(x pr x q x f x x p +=-，r(x)的次数小于n第五章 二次同余式和平方剩余1. 欧拉判别条件定义：m>0,(a,m)=1,若对于整数a ，)(mod 2m a x ≡有解，则称a 是模m 的平方乘余; 否则，称a 是模m 的平方非乘余 2. 欧拉判别定理：p>2,(a,p)=1,则有 (1)a 是模p 的平方乘余的充要条件是)(mod 121p ap ≡- (2)a 是模P 的平方非乘余充要条件是)(mod 121p ap -≡-(3)a 是模p 的平方乘余,则)(mod 2p a x ≡有两个解 3.在模P 的简化系中，平方剩余和平方非剩余余各为21-p 个，且21-p 个平方乘余分别与22)21(,2,1-p Λ之一同余，而且仅与一数一同余4.勒让德符号：p 是一个给定的奇素数，对于整数a 定义勒让德符号⎪⎩⎪⎨⎧-=a p a a p a |,0是平方剩余,1是平方剩余,1)( 5. 勒让德符号的一些性质：(1) )(mod )(21p apap -≡(2) )()(),(mod p bp a p b a =⇒≡(3) )())(()(2121pap a p a p a a a k k ΛΛ= (4) 1)1(=p(5) ⎩⎨⎧+=-+==-=--34,114,1)1()1(21k p k p p p(6)二次互反律：设p ，q 是两个不同的奇素数，则有)()1()(2121qp pqq p -⋅--=6.雅可比符号：给定正奇数m=k p p p Λ21对任意的整数a 定义)())(()(21k p a p a p a ma Λ=，称)(ma 为雅可比符号（注意：1、雅可比符号是勒让德符号 的推广；2、雅可比符号为1时，)(mod 2m a x ≡不一定有解；3、雅可比符号为-1时，则)(mod 2m a x ≡一定无解） 雅可比符号继承了勒让德符号的所有性质7. 合数模二次同余方程 设P 是奇素数，（a ，p ）=1，则有（1）若)(p a=-1，则)(mod 2αp a x ≡无解（2）若)(p a=1，则)(mod 2αp a x ≡有两解8.若(a,2)=1，则（1）α=1时，)2(mod 2αa x ≡有一解（2）α=2时，)2(mod 2αa x ≡有解的的充要条件是a=4k+1，且若有解，则有两解（3）3≥α时，则)2(mod 2αa x ≡有解的充要条件是a=8k+1，且若有解，则有四解。
