基础数论四大定理

TIPS：本文共有 1693 个字，阅读大概需要 4 分钟。

1、威尔逊定理

当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )

或者这么写( p -1 )! ≡ p-1 ( mod p )

或者说若p为质数，则p能被(p-1)!+1整除

2、欧拉定理

欧拉定理，也称费马-欧拉定理

若n，a为正整数，且n，a互质，即gcd(a，n) = 1，则

a^φ(n) ≡ 1 (mod n)

3、孙子定理（中国剩余定理）

用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组

4、费马小定理

假如p是质数，若p不能整除a，则 a^(p-1) ≡1（mod p），若p能整除a，则a^(p-1) ≡0（mod p）。

或者说，若p是质数，且a，p互质，那么 a的(p-1)次方除以p的余数恒等于1。

顺便提一下，费马大定理:当整数n >2时，关于x， y， z的方程 x^n + y^n = z^n 没有正整数解

基础数论四大定理

威尔逊定理、欧拉定理、孙子定理（中国剩余定理）、费马小定理。

数论是纯粹数学的分支之一，主要研究整数的性质。整数可以是方程式的解（丢番图方程）。有些解析函数（像黎曼ζ函数）中包括了一些整数、质数的性质，透过这些函数也可以了解一些数论的问题。

透过数论也可以建立实数和有理数之间的关系，并且用有理数来逼近实数（丢番图逼近）。

按研究方法来看，数论大致可分为初等数论和高等数论。

初等数论是用初等方法研究的数论，它的研究方法本质上说，就是利用整数环的整除性质，主要包括整除理论、同余理论、连分数理论。高等数论则包括了更为深刻的数学研究工具。

基础数论四大定理

威尔逊定理、欧拉定理、孙子定理（中国剩余定理）、费马小定理并称数论四大定理。

威尔逊定理

概念

p可整除(p-1)!+1是p为质数的充要条件

证明

充分性

如果p不是素数

当p=4时，显然（p-1)!≡6≡2(mod p)

当p>4时，若p不是完全平方数，则存在两个不等的因数a，b使得ab=p

则(p-1)!≡nab≡0(mod p)

若p是完全平方数即p=k^2，因为p>4，所以k>2，k，2k<p

(p-1)!≡n(k*2k)≡n'k^2≡0(mod p)。

必要性

若p是素数，取集合 A={1，2，3，...p -1} 则A 构成模p乘法的缩系，即任意i∈A ，存在j∈A，使得:( i j ) ≡ 1 ( mod p )

那么A中的元素是不是恰好两两配对呢?

不一定，但只需考虑这种情况x^2 ≡ 1 ( mod p )

解得: x ≡ 1 ( mod p ) 或 x ≡ p - 1 ( mod p )

其余两两配对故而( p - 1 )! ≡ 1﹡( p -1 ) ≡ -1 ( mod p )

欧拉定理

概念

欧拉定理，也称费马-欧拉定理。

若n，a为正整数，且n，a互素，即gcd(a，n) = 1，则

a^φ(n) ≡ 1 (mod n)

证明

设x（1），x（2），...，x(φ(n))是一个以n为模的缩系

则ax（1），ax（2），...，ax（φ(n) ）也是一个以n为模的缩系（因为（a，n）=1）。

于是有ax（1）ax（2）...ax（φ(n) ）≡x（1）x（2）...x(φ(n))（mod n）

所以a^φ(n) ≡ 1 (mod n)。证毕。

孙子定理

概念

孙子定理，又称中国剩余定理。

中国剩余定理说明：假设整数m1，m2， ... ，mn两两互质，则对任意的整数：a1，a2， ... ，an，方程组S有解，并可构造得出。构造详见词条“中国剩余定理”。

证明

将构造结果代入验证即可。

费马小定理

概念

假如p是质数，若p不能整除a，则 a^(p-1) ≡1（mod p），若p能整除a，则a^(p-1) ≡0（mod p）。

若p是质数，且a，p互质，那么 a的(p-1)次方除以p的余数恒等于1。

证明

因为p是质数，且（a，p)=1，所以φ(p)=p-1。

由欧拉定理可得a^(p-1) ≡1（mod p）。证毕。

对于该式又有a^p ≡a（mod p），而且此式不需要（a，p）=1

所以，费马小定理的另一种表述为：假如p是质数，a是整数，那么a^p ≡a（mod p）。

如果觉得《基础数论四大定理》对你有帮助，请点赞、收藏，并留下你的观点哦！