数论四大定理

朴灿烈づ我的快乐病毒、 2021-12-21 23:23 1031阅读 0赞

## 威尔逊定理 ##

### 概念 ###

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

## 欧拉定理 ##

### 概念 ###

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

若n,a为正整数，且n,a互素，即  gcd(a,n) = 1，则  a^φ(n) ≡ 1 (mod n)

## 扩展欧拉定理 ##

### 概念 ###

**![1253846-20190213153142000-1660037390.png][]**

## 费马小定理 ##

## 概念 ##

若 n 是质数，a%n !=0，则   a^(n-1) ≡1（mod n）;

a%n ==0，则   a^(n-1) ≡0（mod n)

若 n 是质数，gcd(a,n) =1，a^φ(n) =n-1，则 a^(n-1)≡0（mod n)

##  孙子定理 ##

### 概念 ###

求满足 n%A=a && n%B=b 的数

则 n = ( k1\*B\*a + k2\*A\*b )% lcm( A,B ) + m \* lcm( A,B );　　// k1\*B%A = k2\*A%B = 1;

此时，显然可得，n%A=a && n%B=b ;

推广一下：

设 Gi=∏(A...) /Ai;

n = ∑(ki\*Gi\*gi) %lcm(A...) +m\*lcm(A...);　　//Gi\*gi%Ai = 1;

附：三大定理的证明（定理的引用参考《初等数论及其应用》）

作者：synapse7  
来源：CSDN  
原文：https://blog.csdn.net/synapse7/article/details/19610361

一、威尔逊定理  
  
(PS:在利用定理4.10时，仅需用到a^-1的存在性；证明中的“只有”二字要用定理4.11中的“唯一性”)  
![1253846-20190213153416311-453403840.png][]

![1253846-20190213153428102-1850199579.png][]

二、欧拉定理  
  
证明前，我们先定义一个概念：  
![1253846-20190213153529261-1003521090.png][]

![1253846-20190213153551308-838976441.png][]

三、费马小定理  
  
重申一遍，gcd(a,p)=1  
![1253846-20190213153448527-748471775.png][]

转载于:https://www.cnblogs.com/canchan/p/10370381.html

[1253846-20190213153142000-1660037390.png]: /images/20211220/837dd284cb6248b59454d4bbcf6065bd.png
[1253846-20190213153416311-453403840.png]: /images/20211220/a75211fa2d344b239aa6411cd61d9899.png
[1253846-20190213153428102-1850199579.png]: /images/20211220/5f2e5a4a49004fbdbd8c2cca80496c55.png
[1253846-20190213153529261-1003521090.png]: /images/20211220/7b42ffcc2df04860ae95cce426a3f475.png
[1253846-20190213153551308-838976441.png]: /images/20211220/14ca46c38ef449ed84edbc71be12417a.png
[1253846-20190213153448527-748471775.png]: /images/20211220/5d5e6a2812624ced86b2fbdb47ba46b3.png