欧拉定理简化剩余系-初等数论基础

本节介绍简化剩余系的基本理论并用它来证明著名的欧拉定理.先回忆一下欧拉函数的概念.设m是正整数.用φ（m）表示序列0，1，2，…，m-1中与m互素的数的个数.φ（m）称为m的欧拉函数值.下面介绍简化剩余系的概念.

定义4.3.1　设m是正整数.称模m的剩余类Ki与m互素，若Ki中每个元素均与m互素.从与m互素的模m的剩余类中各取一个元素组成的集合称为模m的一个简化剩余系.

命题4.3.2　模m的剩余类Ki与m互素当且仅当Ki中某个元素与m互素.

证明　必要性显然.下证充分性.设b∈Ki且（b，m）=1.则关于任意a∈Ki，有m|a-b.故存在q∈Z使得a=qm+b.于是（a，m）=（m，b）=1.证毕.

推论4.3.3　设m是正整数，i∈｛0，1，…，m-1｝.则模m的剩余类Ki与m互素当且仅当（i，m）=1.于是，模m的剩余类中与m互素的有φ（m）个，从而模m的任意简化剩余系中均含φ（m）个元素.

下述命题是显然的.

命题4.3.4　设m是正整数，a1，a2，…，aφ（m）∈Z.则a1，a2，…，aφ（m）是模m的简化剩余系当且仅当a1，a2，…，aφ（m）与m互素且两两对模m不同余.

定义4.3.5　设m是大于1的正整数.则0，1，2，…，m-1中与m互素的数构成的集合是模m的简化剩余系，称其为模m的最小正简化剩余系.

下面的命题指出了模m的两个简化剩余系之间的关系.事实上，命题4.3.6的结论对完全剩余系也是正确的.

命题4.3.6　设m是正整数，a1，a2，…，aφ（m）和b1，b2，…，bφ（m）是模m的两个简化剩余系，n是任意正整数.则

证明　因为a1，a2，…，aφ（m）和b1，b2，…，bφ（m）是模m的两个简化剩余系，从而有ak≡bjk（modm），k=1，2，…，φ（m），其中j1，j2，…，jφ（m）是1，2，…，φ（m）的某个排列.于是

另外，对任意正整数n，有），k=1，2，…，φ（m），进而有

与完全剩余系一样，一定条件下，由老简化剩余系可构造新简化剩余系.

命题4.3.7　设m是正整数.若（a，m）=1且a1，a2，…，aφ（m）是模m的简化剩余系.则aa1，aa2，…，aaφ（m）也是模m的简化剩余系.

证明　类似于命题4.2.5可证明aa1，aa2，…，aaφ（m）对模m两两不同余.由a1，a2，…，aφ（m）是模m的简化剩余系知诸ai均与m互素.注意到（a，m）=1，有（aai，m）=1.据命题4.3.4，aa1，aa2，…，aaφ（m）也是模m的简化剩余系.证毕.

例4.3.8　设p是奇素数，m是正整数且-1.证明

1m+2m+…+（p-1）m≡0（modp）.

证明　由p是奇素数知（2，p）=1，而1，2，…，p-1是模p的简化剩余系.由命题4.3.7可知2×1，2×2，…，2×（p-1）也是模p的简化剩余系.由命题4.3.6知(www.xing528.com)

这表明

由及p是素数知（p，2m-1）=1.据命题4.1.4（3），结论成立.证毕.

本节最后叙述著名的欧拉定理及费马小定理，同时考虑其若干应用.

定理4.3.9（欧拉定理）　设m是大于1的整数，（a，m）=1.则

证明　设r1，r2，…，rφ（m）是模m的简化剩余系.则诸rj均与m互素.由命题4.3.7及事实（a，m）=1知ar1，ar2，…，arφ（m）也是模m的简化剩余系.据命题4.3.6，

即aφ（m）r1r2…rφ（m）≡r1r2…rφ（m）（modm）.但r1，r2，…，rφ（m）是模m的简化剩余系，故（ri，m）=1，i=1，2，…，φ（m），据命题1.2.9（5），有（r1r2…rφ（m），m）=1.由命题4.1.4（3），aφ（m）≡1（modm）.证毕.

推论4.3.10（费马小定理）　若p是素数，a∈Z，则ap≡a（modp）.

证明　由p是素数知p|a或（a，p）=1.若p|a，则显然有ap≡a（modp）.若（a，p）=1，则由欧拉定理知ap-1=aφ（p）≡1（modp），两边乘a便得ap≡a（modp）.证毕.

例4.3.11　设p，q是互异素数.则pq-1+qp-1≡1（modpq）.

证明　由p，q互异知（p，q）=1.据欧拉定理，有pq-1≡1（modq）和qp-1≡1（modp）.注意到p，q皆大于1，有qp-1≡0（modq）和pq-1≡0（modp）.于是，

pq-1+qp-1≡1（modq），qp-1+pq-1≡1（modp）.

由于（p，q）=1，据命题4.1.4（4），pq-1+qp-1≡1（modpq）.证毕.

例4.3.12　证明4n+1型素数有无限个.

证明　设p1，p2，…，pm是所有4n+1型素数.记a=4t2+1，t=p1p2…pm.则a是合数，从而a必有素因数.设p是a的素因数.则p必为4n+3型素数，记p=4k+3.由p|a可知4t2≡-1（modp），即（2t）2≡-1（modp）.另一方面，由p=4k+3知（2，p）=（pi，p）=1，i=1，2，…，m，从而（2t，p）=1.据欧拉定理，有

-1=（-1）2k+1≡（（2t）2）2k+1=（2t）4k+2=（2t）p-1=（2t）φ（p）≡1（modp），

这导致p|2，矛盾.证毕.