欧拉定理、费马小定理、孙子定理
1、设m0，则模m有m个剩余类MiikmkZi012m1如果i与m互质，那么Mi中每一个数均与m互质，这样的同余类共有m个
m是1，，m中与m互质的个数，称为欧拉函数；2，
2、欧拉定理：设m1，m1则am1modma
3、缩系的几种性质：1、模m的一组缩系含有m个数；2、若a1、a2、am是m个与m互质的整数，则a1、a2、a（m）是模m的一组缩系的充要条件是aiaimodmii3、若am1且x是通过模m的缩系，则ax也是通过模m的缩系；4、费马小定理：若p为素数，则apamodp
5、若
的标准分解为：
p11p22pkk，则：

1
11111p1p2pk
6、孙子定理：设m1、m2、mk是k个两两互质的正整数，设mm1m2mkmmiMii12kMim1m2mi1mi1mk则同余方程组xb1modm1xb2modm2xbkmodmk
有唯一解xM1M1b1M2M2b2MkMkbkmodm
其中MiMi1modmii12k
例1、设a1、a2、a
和b1、b2、b
分别是
的一组完全剩余系，且2
，求证：a1b1、a2b2、a
b
不是
的一组完全剩余系。证：a1、a2、a
是
的一组完全剩余系，则：
aii
i1i1
i1




1
mod
22
mod
2
同理有：bi

选自《奥林匹克数学》高三分册P61
aibi
mod
0mod
i1
又另一方面aibi也是一组完全剩余系，则有：
a
i1


i
bi

mod
2
2
0

上式不成立，原命题成立；2
1
f例2、证明：数列2
3中有一个无穷子数列，其中任意两项互素；证明：设数列2
3中已有k项是两两互素的，记为u1u2uk作uk12u1u2uk13其中x是欧拉函数，由欧拉定理有：
2u1u2uk＝2u1）u2）uk1modui1ik
选自《奥林匹克数学》高三分册P63
2u1u2uk131modui1ik数列u1u2uk、uk1是k1项两两互素的子数列，依此方法一直下去数列2
3中一定有一个任意两项互素的无穷子数列ui
例3、在12p中有多少个数是与p互质，并求pp为素数。解p为素数问题即为：2p中有多少个数是与p互质，并求p1又在12p中是p的倍数有：p，2p，3p，，p1p1其r