数论四大定理及证明

记录笔者学习数论及其证明知识的过程。

欧拉定理

$$\begin{aligned} & a^{\phi(n)} \equiv 1 \pmod n\\ & phi(n)代表的是1到n中与n互质的数的个数，取集合X={x_1,x_2,...x_{\phi(n)}}来代表这些数\\ & 另取集合M={m_1,m_2,...m_{\phi(n)}}，使m_i=a*x_i(取a与n互质)\\ \end{aligned}$$

即证明

根据X集合中数的性质，首先是X中每个数都不相同，其次是X中每个数与n互质。

要研究的是两集合在模n下的性质，再细究就是首先X中每个数模n都不同余，其次是X中每个数模n与n互质。

来验证M集合是否满足这两性质

1. M中的每个数在模n下都不同余

2. M中每个数模n与n互质

​

$$\begin{aligned} &因为m_i=a*x_i，a、x_i都和n互质,\\ &所以m_i也与n互质\\ &又因为扩展欧几里得定理\\ &所以gcd(m_i,n)=gcd(n,m_i \pmod n)=1\\ \end{aligned}$$

得到M集合与X集合在模n下存在双射关系

因而有

$$\begin{aligned} &m_1∗m_2∗……∗m_{φ(n)}≡x_1∗x_2∗……∗x_{φ(n)}(modn)\\ &a∗x_1∗a∗x_2∗...…∗a∗x_{φ(n)}≡x_1∗x_2∗……∗x_{φ(n)}(modn)\\ &a^{φ(n)}∗(x_1∗x_2……∗x_{φ(n)})≡x_1∗x_2……∗x_{φ(n)}(modn)\\ &a^{φ(n)−1}∗(x_1∗x_2……∗x_{φ(n)})≡0(modn)\\ &然后，由于(x_1∗x_2……∗x_{φ(n)})!≡0(modn)\\ &所以 (a^{φ(n)}−1)≡0(modn)\\ &所以 a^{φ(n)}≡1(modn)\\ \end{aligned}$$

费马小定理

$$\begin{aligned} &对于质数p，任意整数a，均满足：a^{p−1}≡1(modp)\\ &拆开来看a^{p−2}*a≡1(modp),a^{p−2},就是a在模p下的逆元了\\ \end{aligned}$$

中国剩余定理（CRT）

$$\begin{aligned} &设正整数m_1,m_2…m_k两两互素，则同余方程组\\ &x≡a_1\pmod {m_1}\\ &x≡a_2\pmod {m_2}\\ &x≡a_3\pmod{m_3}\\ &…\\ &x≡a_k\pmod{m_k}\\ &有整数解。并且在模M=m_1⋅m_2⋅…⋅m_k下的解是唯一的，解为\\ &x≡(a_1*M_1*M_1^{-1}+a_2*M_2*M_2^{-1}+…+a_k*M_k*M_k^{-1})modM\\ &其中M_i=M/m_i，而M_i为M_i模m_i的逆元。\\ \end{aligned}$$

举个例子来理解证明过程

x≡2(mod3)

x≡3(mod5)

x≡2(mod7)

令x=a+b+c

根据同余的加法：

x%m1 =(a+b+c)%m1=(a%m1+b%m1+c%m1)%m1

从接下来的取法当中可以看出：取a时，b、c必满足是m1的倍数，则满足x的一个解就得到了

令

a≡2(mod3)

a≡0(mod5)

a≡0(mod7)

=> a=5*7p=35p（可以看到p取1的时候满足a≡2(mod3),即a=35）

b≡0(mod3)

b≡3(mod5)

b≡0(mod7)

=>b=21q (可以看到q取3的时候满足b≡3(mod5),即b=63)

c≡0(mod3)

c≡0(mod5)

c≡2(mod7)

=>c=15m(可以看到m取2的时候满足c≡2(mod7),即c=30)

得到一个满足所有等式的x

x≡2(mod3)≡a+b+c

x≡3(mod5)≡a+b+c

x≡2(mod7)≡a+b+c

我们要得到通解，就要利用同余的乘法

令2 a’≡2(mod3),3 b’≡3(mod5),2*c’≡2(mod7)

重复上述过程

a′≡1(mod3)

a′≡0(mod5)

a′≡0(mod7)

=>a′=35p(可以看到p取2的时候满足a′≡1(mod3),即a′=70)

b′≡0(mod3)

b′≡1(mod5)

b′≡0(mod7)

=>b′=21q(可以看到q取1的时候满足b′≡1(mod5),即b′=21)

c′≡0(mod3)

c′≡0(mod5)

c′≡1(mod7)

=>c′=15m(可以看到m取1的时候满足c′≡1(mod7),即c′=15)

有了a′b′c′之后就可以得到 x=2a′+3b′+2∗c′
代入a′b′c′之后就可以得到x的一个解及其通解

x=233+105t

以上面过程求通解的过程来证明

$$\begin{aligned} &直接令a_1'=1\pmod {m_1}\\ &又令k_1*M_1=a_1'\\ & k_1=a_1'*M_1^{-1}\\ &得到x_1=a_1*k_1*M_1=a_1*a_1'*M_1^{-1}*M_1\\ &而a_1'=1\pmod {m_1}\\ &推出x_1\pmod M \equiv a_1*M_1^{-1}*M_1\\ &依次得到x_i(1<=i<=k且k为整数）\\ &x≡x_1+x_2+.....x_i\equiv(a_1*M_1*M_1^{-1}+a_2*M_2*M_2^{-1}+…+a_k*M_k*M_k^{-1})modM\\ \end{aligned}$$

威尔逊定理

设p是一个正整数，那么p是素数的充要条件是

(p-1)!=-1(mod p)

证明如下：

首先证明必要性

若p是素数，那么(p-1)!=-1(mod p)

因为p-1=-1(mod p)

所以只需证明2,3,…p-2的总乘积模p等于1

由于p是奇素数，所以p-2是奇数，从2到p-2共有偶数个数

我们需要用到以下两个证明工具

• 对于素数 p，模 p 的缩系就是 {1,2,3,…,p−1}。（因为所有小于 pp 的正整数都与 pp 互质）。

• 对于缩系中的任意一个元素 a，存在唯一的 a‘，使得 a⋅a’≡1(modp)且 a’ 也在缩系中。

这下我们可以知道2,3,…p-2构成一个缩系，且其中两两配对能是对方在模p下的逆元。

必要性证明成立

然后来证明充分性

使用反证法，假设p是不是一个素数

当p=1是(1−1)!=0!=1，而 1≡0(mod1)，并不等于 −1≡0(mod 1)

当p是合数，有p的最小素因子q，满足2<=q<=p-1,

则q必定是1,2,…p-1中的某数，即p|(p-1)!

根据已知条件(p-1)!=-1(mod p)，p|(p-1)!+1，矛盾

假设不成立，充分性成立

参考Van1sh师傅的博客https://jayxv.github.io