数论重要定理.doc

一 、欧拉定理
设的整数，.

例1 设，求的末三位数.
解 由二项式定理，
是一个正整数.
记，因为
.
而是一个正整数，则所以
于是

又因为
，
，

，
又

所以
， ，
，
则
，
所以

则

因为

所以
，
于是，有
，
，
又因为
，
，
所以
，
即
，
所以
，
于是，有
.
所以

所以
.
故的末三位数是.

二、费马小定理
（1）为素数，且则
；
（2）为素数，则
.

例2 为整数，证明
.
证明 ，
由于

所以
.
即
.
由于奇数的4次方被16除余1，偶数的4次方被16除余0，故有
.
即
.
又由于

则
，
即
.
又两两互素，故.

例3 设整数，求证不是素数.
证明 由于

所以
，
即
.
又

，
同理

则
.
即.
从而不是素数.

例4 设中有无穷多项被整除.
证明 当
当，所以对任意的，即.特别地，取.则
.
令则，即.

三、威尔逊定理
设

.
证明 考虑多项式.
由费马小定理，当

所以则
.则设
.
得，则
.
取代入，得

所以
.
例5 .证明：若为奇素数，则
.
证明：

.
而为奇素数，有.

四、中国剩余定理
设

有整数解.令
则同余方程组在模下的解是唯一的.
令
，
则解为
.

例6 证明：对任意给定的正整数其中每一个都有大于.
分析：

则
.
证明： 设

存在正整数解，设为一个正整数解，则满足要求.
例7 任给正整数，存在
证明 设，同余方程组

存在正整数解

例8 给定正整数，设是使能被整除的最小正整数.证明：当且仅当为2的幂时，有.
分析：，因为
，所以.
则问题归结为：

证明：（1）当.
当
∵，
∴.
∴
综上，知.
（2）分析：.
（证明）
令此时需证，即证存在即可.
构造同余方程组
（1）
由中国剩余定理知，同余方程组（1）有正整数解，则
.从而有，即，
.
考虑的取值范围：
若这与
相矛盾，故.
若，这与
相矛盾,故.
从而有，于是得证.

五、阶及应用
定理1 设

.
证明： 互质，所以有
.
由抽屉原则，使得
，
，
令.

定义1：设
.
注：若
.
当.
定理2 设，则
证明：令，则
.
而，所以.而
知.
从而
推论：若
.
特例：当时，.

例9 设
证明：显然
假设
∵，
∴， ，
∴.
设 ①
又由小费马定理知，，
∴. ②
由①，②知，.
∵
∴.
又若奇数
∵
∴.
∴
由，即.
由知，即，从而

而则.