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

p11
p22

p
k
k
，
则
：

111111
p1
p2
pk
6、孙子定理：设m1、m2、mk是k个两两互质的正整数，设mm1m2mkmmiMi
i12kMim1m2mim1i1mk则同余方程组
xb1modm1
xb2modm2

xbkmodmk
有唯一解x
M
1
M
1b1

M
2
M
2b2


M
k
M
k
bk
mod
m
其
中M
i
M
i
1modmii
12
k
例1、设a1、a2、a
和b1、b2、b
分别是
的一组完全剩余系，且2
，
求证：a1b1、a2b2、a
b
不是
的一组完全剩余系。
证：a1、a2、a
是
的一组完全剩余系，则：

ai
i1


i
i1


12


mod
2
同理有：

i1
bi


mod
2
选自《奥林匹克数学》高三分册P61

aibi
mod
0mod
i1
又另一方面aibi也是一组完全剩余系，则有：

i1
ai
bi


2
mod

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