高二数学竞赛班二试数论讲义-欧拉、威尔逊定理-2

高二数学竞赛班二试讲义

             第2讲  欧拉定理、威尔逊定理

 

班级              姓名           

 

一、知识点金

1．算术基本定理：任何一个正整数，都可以唯一分解成素因数乘积的形式，

其中。均为素数，为非负整数。

记是的正约数的个数，是的正约数的和，则，

2．为平方数的充分必要条件是为奇数

3．完系和缩系：在模的个剩余类中各任取一个数作为代表，这样的个数称为模的一个完全剩余系，简称完系。如果和互素，则易知同余类中所有数都和互素，这样的同余类称为模缩同余类，我们将模缩同余类的个数记作，称为欧拉函数。

   在个缩同余类中各任取一个数作为代表，这样的个数称为模的一个缩剩余系，简称缩系（也称简系）。

4．设，是任意整数。

（i）是模的完系。叫做模的生成元。

（ii）若是模的完系，则也是模的完系。

（iii）若是模的缩系，则也是模的缩系。

证明：，

（i）假设，，则，因为，所以，矛盾！

（ii）假设，，则，所以，矛盾！

（iii），假设，，则，矛盾！

5．欧拉函数，它表示不大于且与互素的正整数的个数，设，均为素数，则。

因此，若，则

证明：由容斥原理

因为，则没有相同素因子，由公式易得

6．欧拉定理：设，则

证明：当时，若是模的缩系，

则也是模的缩系。

  所以，即，所以

费尔马小定理：为素数，且，则。

    即为素数，且，

   证明：当为素数，且时，，，由欧拉定理得

费尔马小定理的推论：为素数，对任意正整数，都有。

7．威尔逊定理：设为素数，则

证明：若，则由4（iii）可知，存在使得。我们称为关于模的逆，记作或。

当时结论显然成立。如，由上述结论知，对每个，，有唯一的，使得

当时，等价于，则

所以个数可配为对，每对满足。

因此，

二、例题分析

例1．（1）证明：完全平方数模4同余于0或1

    （2）证明：奇数的平方模8同余于1

（3）证明：完全立方数模9同余于0，1

 

 

 

 

 

 

 

 

 

 

例2．设是奇数，为正整数，证明：

 

 

 

 

 

 

 

 

 

 

 

 

例3．设是不同的奇素数，，则，反之亦然。