初等数论四大定理

初等数论1. 整除性质a) 若a|b，a|c，则a|(b±c)。

b) 若a|b，则对任意c，a|bc。

c) 对任意非零整数a，±1|a，±a|a。

d) 若a|b，b|a，则|a|=|b|。

e) 如果a能被b整除，c是任意整数，那么积ac也能被b整除。

f) 如果a同时被b与c整除，并且b与c互质，那么a一定能被积bc整除，反过来也成立。

g) 如果a∣b且b∣c，则a∣c。

h) 如果c∣a且c∣b，则c∣ua+vb，其中u，v是整数。

i) 对任意整数a，b，b>0，存在唯一的数对q，r，使a=bq+r，其中0≤r<b，这个事实称为带余除法定理，是整除理论的基础。

j) 若c|a，c|b，则称c是a，b的公因数。

若d是a，b的公因数，d≥0，且d可被a，b的任意公因数整除，则d是a，b的最大公因数。

若a，b的最大公因数等于1，则称a，b互素，也称互质。

累次利用带余除法可以求出a，b的最大公因数，这种方法常称为辗转相除法。

又称欧几里得算法。

2. 带余除法a) 对于a，b两个整数，其中b≠0，则存在唯一q，r使得：a = bq+r，0 ≤ r< |b|．r称为a被b除得到的余数．显然当r = 0时，b∣a．3. 最大公约数设a，b是两个整数，如果整数c∣a且c∣b，则c称为a，b的公因子．设c>0是两个不全为零的整数a，b的公因子，如果a，b的任何公因子都整除c，则c称为a，b的最大公因子，记为c= (a，b)．a) (a,b)=(-a,b)=(a,-b)=(-a,-b)b) (0,a)=ac) 设a，b是两个不全为零的整数，则存在两个整数u，v，使(a，b)= ua+vb．4. 欧几里德除法（辗转相除法）：已知整数a，b，记r0=a，r1=b，r0=q1r1+r2，0 ≤r2＜r1=b;r1=q2r2+r3，0 ≤r3＜r2;…r n-2=q n-1r n-1+r n，0 ≤r n＜r n-1;r n-1=q n r nf) 除法若ac ≡ bc (mod m) c≠0 则a≡ b (mod m/gcd(c,m)) 其中gcd(c,m)表示c,m的最大公约数，特殊地,gcd(c,m)=1 则a ≡ b (mod m)g) 幂运算如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)h) 如果a ≡ b (mod m)，且d∣m，d是正整数，则a ≡ b (mod d)i) 若a ≡ b (mod mi) (i=1,2...n) 则a ≡ b (mod [m1,m2,...mn]) 其中[m1,m2,...mn]表示m1,m2,...mn的最小公倍数j) 推论如果a1≡b1 (mod m)，a2≡b2 (mod m)，则a1x+ a2y≡b1x+ b2y (mod m)，其中x，y是任意整数．a1n=b1n(mod m)，其中n是正整数．f(a1) ≡f(b1) (mod m)，其中f(x)是任一给定的整系数多项式：f(x) = c0+ c1x+…+c k x k．10. 威尔逊定理若p为质数，则p可整除(p-1)!+1。

第五节 初等数论中的几个重要定理基础知识定义（欧拉(Euler)函数）一组数s x x x ,,,21 称为是模m 的既约剩余系，如果对任意的s j ≤≤1，1),(=m x j 且对于任意的Z a ∈，若),(m a ＝1，则有且仅有一个j x 是a 对模m 的剩余，即)(mod m x a j ≡。

并定义},,2,1{)(m s m ==ϕ中和m 互质的数的个数，)(m ϕ称为欧拉（Euler ）函数。

这是数论中的非常重要的一个函数，显然1)1(=ϕ，而对于1>m ，)(m ϕ就是1,2，…，1-m 中与m 互素的数的个数，比如说p 是素数，则有1)(-=p p ϕ。

引理：∏⋅=为质数）－（P |P 11)(mP m m ϕ；可用容斥定理来证（证明略）。

定理1：（欧拉（Euler ）定理）设),(m a ＝1，则)(mod 1)(m a m ≡ϕ。

证明：取模m 的一个既约剩余系))((,,,,21m s b b b s ϕ= ，考虑s ab ab ab ,,,21 ，由于a 与m 互质，故)1(s j ab j ≤≤仍与m 互质，且有i ab )1(s j i ab j ≤<≤∀，于是对每个s j ≤≤1都能找到唯一的一个s j ≤≤)(1σ，使得)(mod )(m b ab j j σ≡，这种对应关系σ是一一的，从而)(mod )(mod )(11)(1m b m b ab s j j s j j s j j∏∏∏===≡≡σ，∴))(mod ()(11m b b a sj j s j j s ∏∏==≡。

1),(1=∏=sj j b m ，)(mod 1m a s ≡∴，故)(mod 1)(m a m ≡ϕ。

证毕。

分析与解答：要证)(mod 1)(m a m ≡ϕ，我们得设法找出)(m ϕ个n 相乘，由)(m ϕ个数我们想到m ,,2,1 中与m 互质的)(m ϕ的个数：)(21,,,m a a a ϕ ，由于),(m a ＝1，从而)(21,,,m aa aa aa ϕ 也是与m 互质的)(m ϕ个数，且两两余数不一样，故)(21m a a a ϕ⋅⋅⋅ ≡)(21,,,m aa aa aa ϕ ≡)(m a ϕ)(21m a a a ϕ⋅⋅⋅ （m mod ），而（)(21m a a a ϕ⋅⋅⋅ m ）＝1，故)(mod 1)(m am ≡ϕ。

威尔逊定理：威尔逊定理是以英格兰数学家爱德华·华林的学生约翰·威尔逊命名的，尽管这对师生都未能给出证明。

华林于1770年提出该定理，1773年由拉格朗日首次证明。

在初等数论中，威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。

即：当且仅当p为素数时：但是由于阶乘是呈爆炸增长的，其结论对于实际操作意义不大。

证明充分性如果“p”不是素数，那么它的正因数必然包含在整数1, 2, 3, 4, … , p− 1 中，因此gcd((p− 1)!, p) > 1，所以我们不可能得到(p− 1)! ≡ −1 (mod p)。

必要性若p是素数,取集合; 则A 构成模p乘法的缩系,即任意i∈A ,存在j∈A,使得:那么A中的元素是不是恰好两两配对呢? 不一定,但只需考虑这种情况;解得:或其余两两配对;故而若p不是素数且大于4, 则易知有故而注：百度百科上的证明法二存在错误。

关于A中元素两两配对可以参见法一。

费马小定理是数论中的一个重要定理，其内容为：假如p是质数，且(a,p)=1，那么a p-1≡1（mod p）即：假如p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1一、准备知识：引理1．剩余系定理2若a,b,c为任意3个整数，m为正整数，且（m,c)=1，则当ac≡bc(mod m）时，有a≡b(mod m)证明：ac≡bc(mod m）可得ac–bc≡0(mod m）可得（a-b)c≡0(mod m）因为（m,c)=1即m,c互质，c可以约去，a–b≡0(mod m）可得a≡b(mod m)引理2．剩余系定理5若m为整数且m>1,a[1],a[2],a[3],a[4]，…a[m]为m个整数，若在这m个数中任取2个整数对m不同余，则这m个整数对m构成完全剩余系。

证明：构造m的完全剩余系（0,1,2，…m-1），所有的整数必然这些整数中的1个对模m同余。

取r[1]=0,r[2]=1,r[3]=2,r[4]=3，…r=i-1,1<i<=m。

数论的四⼤定理详解（转载）转载于:前⾔可以发现RSA中的很多攻击⽅法都是从数论四⼤定理推导出的，所以找时间好好学习了⼀下数论四⼤定理的证明及其应⽤场景——Rabin算法。

欧拉定理若$n,a$为正整数，且$n,a$互素，即$gcd(a,n) = 1$，则$a^{φ(n)}\equiv1\pmod{n}$证明⾸先，我们需要知道欧拉定理是什么：数论上的欧拉定理，指的是$a^{φ(n)}\equiv1\pmod{n}$这个式⼦实在$a$和$n$互质的前提下成⽴的。

证明⾸先，我们知道在1到$n$的数中，与n互质的⼀共有$φ(n$)个，所以我们把这$φ(n)$个数拿出来，放到设出的集合X中，即为$x_1,x_2……x_{φ(n)}$那么接下来，我们可以再设出⼀个集合为M，设M中的数为：$m_1=a∗x_1,m_2=a∗x_2……m_φ(n)=a∗x_{φ(n)}$下⾯我们证明两个推理：⼀、M中任意两个数都不模n同余。

反证法。

证明：假设M中存在两个数设为$m_a,m_b$模$n$同余。

即$m_a\equiv m_b$移项得到：$m_a−m_b=n∗k$再将m⽤x来表⽰得到：$a∗x_a−a∗x_b=n∗k$提取公因式得到：$a∗(x_a−x_b)=n∗k$我们现在已知$a$与$n$互质，那么式⼦就可以转化为：$x_a−x_b\equiv 0 \pmod{n}$因为$a$中没有与$n$的公因⼦（1除外）所以$a !\equiv 0 \pmod{n}$ 所有只能是$ x_a−x_b\equiv 0\pmod{n}$。

⼜因为$x_a,x_b$都是⼩于$n$的并且不会相同，那么上述的式⼦⾃然全都不成⽴。

假设不成⽴。

证得：$M$中任意两个数都不模$4$同余。

⼆、M中的数除以n的余数全部与n互质。

证明：我们已知$m_i=a∗x_i$⼜因为$a$与$n$互质，$x_i$与$n$互质，所以可得$m_i$与$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 ,,,21L 都是b 的倍数，则)(|21n a a a b +++L 。

或着i b a |，则∑=ni i i b c a 1|其中n i Z c i ,,2,1,L =∈；(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 L 21|，则p 能整除n a a a ,,,21L 中的某一个；特别地，若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 除得的余数。

初等数论知识点数论是数学的一个重要分支，而初等数论则是数论中较为基础和入门的部分。

它主要研究整数的性质和相互关系，虽然看似简单，却蕴含着深刻的数学思想和广泛的应用。

一、整除整除是初等数论中最基本的概念之一。

如果整数 a 除以整数 b（b≠0），所得的商是整数且没有余数，我们就说 a 能被 b 整除，或者b 能整除 a，记作 b ｜ a。

例如，6 能被 3 整除，因为 6÷3 ＝ 2，没有余数；而 7 不能被 3 整除，因为 7÷3 ＝ 21，有余数 1。

整除具有一些基本性质，比如：1、如果 a ｜ b 且 b ｜ c，那么 a ｜ c。

2、如果 a ｜ b 且 a ｜ c，那么对于任意整数 m、n，有 a ｜（mb＋ nc)。

二、因数和倍数如果 a 能被 b 整除（b≠0），那么 b 就是 a 的因数，a 就是 b 的倍数。

一个数的因数是有限的，其中最大的因数是它本身；一个数的倍数是无限的，其中最小的倍数是它本身。

例如，12 的因数有1、2、3、4、6、12；12 的倍数有12、24、36、48三、质数和合数质数是指一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数。

合数则是指除了能被 1 和本身整除外，还能被其他数（0 除外）整除的自然数。

例如，2、3、5、7 是质数；4、6、8、9 是合数。

1 既不是质数也不是合数。

质数在数论中有着重要的地位，寻找大质数是密码学等领域中的关键问题。

四、公因数和最大公因数几个数公有的因数，叫做这几个数的公因数；其中最大的一个，叫做这几个数的最大公因数。

求最大公因数可以用辗转相除法。

例如，求 24 和 36 的最大公因数，36÷24 ＝ 112，24÷12 ＝ 2，所以24 和 36 的最大公因数是 12。

五、公倍数和最小公倍数几个数公有的倍数，叫做这几个数的公倍数；其中最小的一个，叫做这几个数的最小公倍数。

初等数论知识点整理 1. 整数的基本性质：
- 整数的定义与整数集的基本运算
- 整数的大小与比较
- 整数的不同表示形式（十进制、二进制、八进制等） 2. 整除与约数：
- 整除的定义与性质
- 素数的定义与判定方法
- 约数的定义与性质
- 最大公约数与最小公倍数的概念与计算方法
3. 同余与模运算：
- 同余的定义与性质
- 同余的基本运算性质
- 模运算的基本性质
- 剩余类和完全剩余系的概念与性质
4. 质数与素数：
- 质数与素数的定义
- 质数与素数的性质和特性
- 素数的测试方法与算法
- 质因数分解的方法与应用
5. 数论基本定理：
- 唯一分解定理（素因数分解定理）
- 辗转相除法与欧几里得算法
- 欧拉函数与欧拉定理
- 费马小定理与扩展欧几里得算法
6. 数论问题的应用：
- 同余方程与线性同余方程
- 不定方程的整数解与应用
- 素数分布与素数定理
- 模重复性与周期性问题
注意：本整理的所有内容仅供参考，请勿将其作为官方教材或其他正式场合使用。

初等数论中的几个重要定理基础知识定义（欧拉(Euler)函数）一组数称为是模的既约剩余系，如果对任意的，且对于任意的，若＝1，则有且仅有一个是对模的剩余，即。

并定义中和互质的数的个数，称为欧拉（Euler）函数。

这是数论中的非常重要的一个函数，显然，而对于，就是1,2，…，中与互素的数的个数，比如说是素数，则有。

引理：；可用容斥定理来证（证明略）。

定理1：（欧拉（Euler）定理）设＝1，则。

分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于＝1，从而也是与互质的个数，且两两余数不一样，故（），而（）＝1，故。

证明：取模的一个既约剩余系，考虑，由于与互质，故仍与互质，且有，于是对每个都能找到唯一的一个，使得，这种对应关系是一一的，从而，。

，，故。

证毕。

这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。

定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。

设为质数，若是的倍数，则。

若不是的倍数，则由引理及欧拉定理得，，由此即得。

定理推论：设为质数，是与互质的任一整数，则。

定理3：（威尔逊（Wilson）定理）设为质数，则。

分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。

证明：对于，在中，必然有一个数除以余1，这是因为则好是的一个剩余系去0。

从而对，使得；若，，则，，故对于，有。

即对于不同的对应于不同的，即中数可两两配对，其积除以余1，然后有，使，即与它自己配对，这时，，或，或。

除外，别的数可两两配对，积除以余1。

故。

定义：设为整系数多项式（），我们把含有的一组同余式（）称为同余方组程。

特别地，，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数同时满足：，则剩余类（其中）称为同余方程组的一个解，写作定理4：（中国剩余定理）设是两两互素的正整数，那么对于任意整数，一次同余方程组，必有解，且解可以写为：这里，，以及满足，（即为对模的逆）。

第一章整除理论整除性理论是初等数论的基础。

本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。

第一节数的整除性定义1设a，b是整数，b≠ 0，如果存在整数c，使得a = bc成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号b∣a；如果不存在整数c使得a = bc成立，则称a不被b整除，记为b|/a。

显然每个非零整数a都有约数±1，±a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。

被2整除的整数称为偶数，不被2整除的整数称为奇数。

定理1下面的结论成立：(ⅰ) a∣b⇔±a∣±b；(ⅱ) a∣b，b∣c⇒a∣c；(ⅲ) b∣a i，i = 1, 2, , k⇒b∣a1x1+a2x2+ +a k x k，此处x i（i = 1, 2, , k）是任意的整数；(ⅳ) b∣a ⇒bc∣ac，此处c是任意的非零整数；(ⅴ) b∣a，a≠ 0 ⇒ |b| ≤ |a|；b∣a且|a| < |b| ⇒a = 0。

证明留作习题。

定义2若整数a≠ 0，±1，并且只有约数±1和±a，则称a是素数（或质数）；否则称a为合数。

以后在本书中若无特别说明，素数总是指正素数。

定理2任何大于1的整数a都至少有一个素约数。

证明若a是素数，则定理是显然的。

若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1, d2, , d k 。

不妨设d1是其中最小的。

若d1不是素数，则存在e1 > 1，e2 > 1，使得d1 = e1e2，因此，e1和e2也是a的正的非平凡约数。

这与d1的最小性矛盾。

所以d1是素数。

证毕。

推论证明使用定理2中的记号，有a = d1d2，其中d1 > 1是最小的素约数，所以d12≤a。

证毕。

例1设r是正奇数，证明：对任意的正整数n，有n+ 2|/1r+ 2r+ +n r。