给定模m的一个完全剩余系r1，r2，…，rm，其中ri与m互质的情况非常重要.
例如，12的非负完全剩余系中与12互质的正整数有1，5，7，11四个.也可以说，不超过12又与12互质的正整数有1，5，7，11四个.
以此我们可以证明“大于3的质数的平方可表示为24n＋1的形式”，过程如下：
由于大于3的质数可以表示为p=12q＋t（t=1，2，…，11)，但p为质数，故t必不是合数，只可能是1，5，7，11.无论t取这四个数中的哪一个，p2=（12q＋t)2=144q2＋24qt＋t2≡t2≡1（mod24).
故大于3的质数的平方必可表示为24n＋1的形式.
定义3 不超过正整数m又与m互质的正整数的个数记作φ（m)，叫作欧拉函数.
显然，欧拉函数的定义域和值域都是正整数集.
特别地，φ（1)=1，φ（2)=1，φ（3)=2，φ（4)=2，φ（5)=4，φ（6)=2.当p为质数时，φ（p)=p-1.
定义4 与模m互质的剩余类有φ（m)个，从每类中各取一个数构成的集合，叫作模m的一个简化剩余系；在模m的最小非负完全剩余系中取得的简化剩余系，叫作模m的最小正简化剩余系.
例5 写出模9的最小正简化剩余系和两个简化剩余系.
解 模9的最小非负完全剩余系为0，1，2，3，4，5，6，7，8.
最小正简化剩余系为1，2，4，5，7，8.
写出与模m互质的所有剩余类：
k1，k2，k3，k4，k5，k6取一组整数值即可得到模m的一个简化剩余系，如都取1，依次取0，1，0，1，0，1，分别得到两个简化剩余系：
10，11，13，14，16，17和1，11，4，14，7，17.
定理6 设r1，r2，…，rφ（m)是模m的一个简化剩余系，（a，m)=1，则ar1，ar2，…，arφ（m)也是模m的一个简化剩余系.
证明 若k1≠k2，ark1≡ark2（modm)，则∵（a，m)=1，∴rk1≡rk2（modm)，这与已知矛盾.
故ar1，ar2，…，arφ（m)也是模m的一个简化剩余系.
但若r1，r2，…，rφ（m)是模m的一个简化剩余系，b是任一整数，则r1＋b，r2＋b，…，rφ（m)＋b不一定是模m的一个简化剩余系.
例如，模9的最小正简化剩余系中的各数都加1，所得6个数2，3，5，6，8，9就不能构成模9的一个简化剩余系.
下面我们学习欧拉函数的性质.
定理7 设p为质数，k为正整数，则φ（pk)=pk-1（p-1).(www.xing528.com)
证明 因为p为质数，p有且只有正约数1和p，所以与p不互质的数必为p的倍数.因为与p不互质的充要条件是与pk不互质，故与pk不互质的数即与p不互质的数，也就是p的倍数，
在1至pk这pk个数中，p的倍数有p，2p，3p，…，（pk-1-1)p，pk这pk-1个数与p不互质，而与其互质的有pk-pk-1个，故
例6 求φ（3)，φ（9)，φ（27)，φ（81).
解 φ（3)=31-1（3-1)，
φ（9)=φ（32)=32-1（3-1)=6，
φ（27)=φ（33)=33-1（3-1)=18，
φ（81)=φ（34)=34-1（3-1)=54.
定理8 设m1，m2∊N*，（m1，m2)=1，则φ（m1m2)=φ（m1)φ（m2).
例如，可分别验证φ（5)=4，φ（6)=2，φ（30)=8.
一般证明比较复杂，感兴趣的读者可阅读本书末所列参考书.
定理9 设正整数m的标准分解式为
习题2.2
1.写出模9的一个完全剩余系，使得其中每个数都是奇数.
2.求证：当m＞2时，{02，12，22，…，（m-1)2}必不是模m的一个完全剩余系.
3.写出模5的最小非负完全剩余系和绝对最小完全剩余系，并按同余关系建立这两个完全剩余系的一个一一对应关系.
4.设x1，x2，…，xm是模m的一个完全剩余系，求证：
5.求证：任一整数的立方被7除，所得余数只能是0，1，6三者之一.
6.模200的简化剩余系由多少个数组成？
7.求分母不超过10的所有最简真分数的个数与它们的和.
8.求证：满足φ（m)=14的正整数m不存在.
9.已知正整数N仅有质约数3，5，7，且φ（N)=3600，求N.
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
