文章目录

• 一、导言
• 二、完全剩余系
• 三、既约剩余系
• 四、费马小定理
• 五、威尔逊定理
• 六、二次剩余
• 七、正式论证

一、导言

本文主要论证：任意素数$p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$，均存在正整数$a,b$，满足p=a2+b2p=a^2+b^2p=a2+b2。

为了让不同知识储备的读者能够理解论证过程，本文对一些定理和概念做了一些阐述，如果读者已经掌握了，可以跳过相应的章节。

二、完全剩余系

设正整数$n\ge 2$，若$n$个数a1,…,ana_1,\dots,a_na1​,…,an​取遍$\mathrm{m}\mathrm{o}\mathrm{d}n$的所有余数，即对于任意整数$m$，均存在整数$i$，使得ai≡m(modn)a_i\equiv m\space({\rm mod}\space n)ai​≡m (mod n)，则称a1,…,ana_1,\dots,a_na1​,…,an​构成$\mathrm{m}\mathrm{o}\mathrm{d}n$的完全剩余系，简称完系。

易知完全剩余系有下列性质。

性质1 $\mathrm{m}\mathrm{o}\mathrm{d}n$的两个完系中的元素之和$\mathrm{m}\mathrm{o}\mathrm{d}n$同余。
性质2 $\mathrm{m}\mathrm{o}\mathrm{d}n$的完系的元素之积为$n$的倍数
性质3 完系中每一个元素乘以一个非零整数后依然构成完系。

这三个性质是显然的，就不加以证明了。

三、既约剩余系

设正整数$n\ge 2$，若a1,…,aka_1,\dots,a_ka1​,…,ak​取遍所有与$n$互素的余数，即对于任意整数$m$满足$(m,n)=1$，均存在正整数$i$使得ai≡m(modn)a_i\equiv m\space({\rm mod}\space n)ai​≡m (mod n)，并且a1,…,ana_1,\dots,a_na1​,…,an​两两$\mathrm{m}\mathrm{o}\mathrm{d}n$不同余，则称a1,…,ana_1,\dots,a_na1​,…,an​构成$\mathrm{m}\mathrm{o}\mathrm{d}n$的既约剩余系，简称缩系。

易知既约剩余系有下列性质。

性质1 $\mathrm{m}\mathrm{o}\mathrm{d}n$的两个缩系中的元素之和$\mathrm{m}\mathrm{o}\mathrm{d}n$同余。
性质2 $\mathrm{m}\mathrm{o}\mathrm{d}n$的两个缩系中的元素之积$\mathrm{m}\mathrm{o}\mathrm{d}n$同余。
性质3 缩系中每一个元素乘以与$n$互素的整数依然构成缩系。

这三个性质是显然的，就不加以证明了。

我们规定缩系的元素个数为欧拉函数$\phi (n)$，即$\le n$且与$n$互素的正整数的个数为$\phi (n)$。

特别地，对于素数$p$，因为$1,\dots ,p-1$均与$p$互素，因此$\phi (p)=p-1$。

四、费马小定理

对于素数$p$及整数$m$满足$(m,p)=1$，均有mp−1≡1(modp)m^{p-1}\equiv1\space({\rm mod}\space p)mp−1≡1 (mod p)

证明

考虑$\mathrm{m}\mathrm{o}\mathrm{d}p$的缩系$1,2,\dots ,p-1$，将每一个元素乘以$m$，得$m,2m,\dots ,m(p-1)$，根据缩系的性质3，$m,2m,\dots ,m(p-1)$也构成缩系，再由性质2可知$$1\cdot 2\cdots (p-1)\equiv m\cdot 2m\cdots m(p-1)(\mathrm{m}\mathrm{o}\mathrm{d}p)$$即(p−1)!≡(p−1)!⋅mp−1(modp)(p-1)!\equiv(p-1)!\cdot m^{p-1}\space({\rm mod}\space p)(p−1)!≡(p−1)!⋅mp−1 (mod p)因为$(p-1)!$与$p$互素，因此可以约去mp−1≡1(modp)m^{p-1}\equiv1\space({\rm mod}\space p)mp−1≡1 (mod p)证毕。

由费马小定理也可知，对于任意整数$m$，均有mp−m≡0(modp)m^p-m\equiv0\space({\rm mod}\space p)mp−m≡0 (mod p)

费马小定理也有其推广的形式，即欧拉定理mφ(n)≡1(modn)m^{\varphi(n)}\equiv1\space({\rm mod}\space n)mφ(n)≡1 (mod n)证明方法类似，这里就不再赘述了。

五、威尔逊定理

若$p$为奇素数，则$(p-1)!\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}p)$

证明

对于任意整数$1\le i\le p-1$，均存在整数1≤i−1≤p−11\le i^{-1}\le p-11≤i−1≤p−1，使得i⋅i−1≡1(modp)i\cdot i^{-1}\equiv1\space({\rm mod}\space p)i⋅i−1≡1 (mod p)，称这样的i−1i^{-1}i−1为$i$的逆。

考虑同余方程x≡x−1(modp)⇔x2≡1(modp)⇔(x−1)(x+1)≡0(modp)x\equiv x^{-1}\space({\rm mod}\space p)\Leftrightarrow x^2\equiv1\space({\rm mod}\space p)\Leftrightarrow(x-1)(x+1)\equiv0\space({\rm mod}\space p)x≡x−1 (mod p)⇔x2≡1 (mod p)⇔(x−1)(x+1)≡0 (mod p)，显然该同余方程仅有两个解：$x\equiv \pm 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$，因此仅有$1$和$p-1$的逆是其本身。

显然，可以将$2,\dots ,p-2$分为两组，使得两组对应的数互为逆，记其中一组为a1,…,a(p−3)/2a_1,\dots,a_{(p-3)/2}a1​,…,a(p−3)/2​，则另一组为a1−1,…,a(p−3)/2−1a_1^{-1},\dots,a_{(p-3)/2}^{-1}a1−1​,…,a(p−3)/2−1​，因此2⋅3⋯(p−2)≡a1⋯a(p−3)/2a1−1⋯a(p−3)/2−1≡1(modp)2\cdot3\cdots(p-2)\equiv a_1\cdots a_{(p-3)/2}a_1^{-1}\cdots a_{(p-3)/2}^{-1}\equiv1\space({\rm mod}\space p)2⋅3⋯(p−2)≡a1​⋯a(p−3)/2​a1−1​⋯a(p−3)/2−1​≡1 (mod p)所以$(p-1)!\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}p)$

证毕。

六、二次剩余

设正整数$n\ge 2$，若整数$m$满足，存在整数$x$使得x2≡m(modn)x^2\equiv m\space({\rm mod}\space n)x2≡m (mod n)，则称$m$为$\mathrm{m}\mathrm{o}\mathrm{d}n$的二次剩余；反之，则称$m$为$\mathrm{m}\mathrm{o}\mathrm{d}n$的二次非剩余。本文中的二次剩余均不包括$0$

例如，$\mathrm{m}\mathrm{o}\mathrm{d}2$的二次剩余有$0,1$，$\mathrm{m}\mathrm{o}\mathrm{d}3$的二次剩余有$0,1$，$\mathrm{m}\mathrm{o}\mathrm{d}4$的二次剩余有$0,1$。

设奇素数$p$，$d$为整数，记(dp)≡d(p−1)/2(modp)\left(\frac dp\right)\equiv d^{(p-1)/2}\space({\rm mod}\space p)(pd​)≡d(p−1)/2 (mod p)(勒让德符号)，则(dp)={1,d为二次剩余−1,d为二次非剩余0,d≡0(modp)\left(\frac dp\right)= \left\{\begin{matrix} 1,&d为二次剩余 \\ -1,&d为二次非剩余 \\ 0,&d\equiv0\space({\rm mod}\space p) \end{matrix}\right.(pd​)=⎩⎨⎧​1,−1,0,​d为二次剩余d为二次非剩余d≡0 (mod p)​

证明

若$d$为二次剩余，则存在整数$x$使得x2≡d(modp)x^2\equiv d\space({\rm mod}\space p)x2≡d (mod p)，则(dp)≡d(p−1)/2≡xp−1≡1(modp)\left(\frac dp\right)\equiv d^{(p-1)/2}\equiv x^{p-1}\equiv1\space({\rm mod}\space p)(pd​)≡d(p−1)/2≡xp−1≡1 (mod p)

若$d$为非二次剩余，则对于任意整数$1\le i\le p-1$，均存在$1\le j\le p-1$，使得$ij\equiv d(\mathrm{m}\mathrm{o}\mathrm{d}p)$，并且$i\ne j$（否则，若$i=j$，则$d$为二次剩余）。记$i$对应的$j$为i−1i^{-1}i−1(称作逆)，即i⋅i−1≡d(modp)i\cdot i^{-1}\equiv d\space({\rm mod}\space p)i⋅i−1≡d (mod p)显然，每一个$i$对应唯一的i−1i^{-1}i−1，即$i$与i−1i^{-1}i−1是两两成对的。因此，可以将$1,\dots ,p-1$分为两组，每组含$(p-1)/2$个数，使得两组对应的两数互为逆。记其中一组为a1,…,a(p−1)/2a_1,\dots,a_{(p-1)/2}a1​,…,a(p−1)/2​，则另一组为a1−1,…,a(p−1)/2−1a_1^{-1},\dots,a_{(p-1)/2}^{-1}a1−1​,…,a(p−1)/2−1​，故(dp)≡d(p−1)/2≡∏i=1(p−1)/2(ai⋅ai−1)=1⋅2⋯(p−1)=(p−1)!≡−1(modp)\left(\frac dp\right)\equiv d^{(p-1)/2}\equiv\prod_{i=1}^{(p-1)/2}{(a_i\cdot a_i^{-1})}=1\cdot2\cdots(p-1)=(p-1)!\equiv-1\space({\rm mod}\space p)(pd​)≡d(p−1)/2≡i=1∏(p−1)/2​(ai​⋅ai−1​)=1⋅2⋯(p−1)=(p−1)!≡−1 (mod p)

若$d\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)$，显然(dp)=0\left(\frac dp\right)=0(pd​)=0。

证毕。

七、正式论证

设素数$p$满足$p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$，则存在正整数$a,b$，使得p=a2+b2p=a^2+b^2p=a2+b2。

因为$p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$，所以(−1p)≡(−1)(p−1)/2≡1(modp)\left(\frac{-1}p\right)\equiv(-1)^{(p-1)/2}\equiv1({\rm mod}\space p)(p−1​)≡(−1)(p−1)/2≡1(mod p)故$-1$是$\mathrm{m}\mathrm{o}\mathrm{d}p$的二次剩余，因此存在整数$i$使得i2≡−1(modp)i^2\equiv-1\space({\rm mod}\space p)i2≡−1 (mod p)。

考虑$u+vi$，其中$u,v$均为整数且满足0≤u,v0≤u,v<p​，则$u,v$各有[p]+1[\sqrt p]+1[p​]+1种取值，故$u+vi$有([p]+1)2>p([\sqrt p]+1)^2>p([p​]+1)2>p种取值，因此存在(u1,v1)≠(u2,v2)(u_1,v_1)\ne(u_2,v_2)(u1​,v1​)​=(u2​,v2​)满足u1+v1i≡u2+v2i(modp)u_1+v_1i\equiv u_2+v_2i\space({\rm mod}\space p)u1​+v1​i≡u2​+v2​i (mod p)移项得u1−u2≡−i(v1−v2)(modp)u_1-u_2\equiv-i(v_1-v_2)\space({\rm mod}\space p)u1​−u2​≡−i(v1​−v2​) (mod p)两边同时平方得(u1−u2)2≡−(v1−v2)2(modp)(u_1-u_2)^2\equiv-(v_1-v_2)^2\space({\rm mod}\space p)(u1​−u2​)2≡−(v1​−v2​)2 (mod p)即(u1−u2)2+(v1−v2)2≡0(modp)(u_1-u_2)^2+(v_1-v_2)^2\equiv0\space({\rm mod}\space p)(u1​−u2​)2+(v1​−v2​)2≡0 (mod p)取a=∣u1−u2∣,b=∣v1−v2∣a=|u_1-u_2|,b=|v_1-v_2|a=∣u1​−u2​∣,b=∣v1​−v2​∣得a2+b2≡0(modp)a^2+b^2\equiv0\space({\rm mod}\space p)a2+b2≡0 (mod p)。

又因为0≤u,v0≤u,v<p​，因此0≤a2,b20≤a2,b2<p，故a2+b2<2pa^2+b^2<2pa2+b2<2p，因此a2+b2=pa^2+b^2=pa2+b2=p证毕。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！