数学讲义同余的应用

《数学讲义同余的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.数论讲义定义（欧拉(Euler)函数）对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n)（1）对于给定的一个素数p，φ(p)=p-1。（2）则对于正整数n=pk，φ(n)=pk-pk-1欧拉(Euler)函数公式：例1与300互素且不超过300的自然数的个数。解所求的数即　　　　　　　　　　例21到1001这1001个数中，是7,11或13的倍数的有多少个？解：由于7,11,13均为质数，所有不是它们的倍数的数都是和它们互素的，而与它们互素就意味着和1001互素，且这些数都是比1001小的数。所以我们可以直接使用定理1：（欧拉（Euler）定理）设＝1，则。分析与解答

2、：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于＝1，从而也是与互质的个数，且两两余数不一样，故（），而（）＝1，故。这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。例3.设，求证：。...证明：因为，故由知，从而，但是，故由欧拉定理得：，，从而；同理，。于是，，即。定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。设为质数，若是的倍数，则。若不是的倍数，则由引理及欧拉定理得，，由此即得。定理推论：设为质数，是与互质的任一整数，则。例4．求证：对于任意整数，是一个整数。证明：令，则只需证是15的倍数即可。由3，5是素

3、数及Fetmat小定理得，，则；...而（3，5）=1，故，即是15的倍数。所以是整数。例6．求证：（为任意整数）。证明：令，则；所以含有因式由Fetmat小定理，知13

4、7

5、又13，7，5，3，2两两互素，所以2730=能整除。例7．设是直角三角形的三边长。如果是整数，求证：可以被30整除。证明：不妨设是直角三角形的斜边长，则。若2，2，2c，则，又因为矛盾！所以2

6、.若3，3，3c，因为，则，又，矛盾！从而3

7、.若5，5，5c，因为，，所以或0(mod5)与矛盾！从而5

8、.又(2,3,5)=1，所以30

9、.定理3：（威尔逊（Wilson）定理）设为质数，则。分析与解答：受欧拉定理的影响，

10、我们也找个数，然后来对应乘法。证明：对于，在中，必然有一个数除以余1，这是因为则好是的一个完全剩余系去0。　从而对，使得；...　若，，则，，故对于，有　。即对于不同的对应于不同的，即中数可两两配对，其积除以余1，然后有，使，即与它自己配对，这时，，或，或。　　除外，别的数可两两配对，积除以余1。故。定义：设为整系数多项式（），我们把含有的一组同余式（）称为同余方组程。特别地，，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数同时满足：，则剩余类（其中）称为同余方程组的一个解，写作定理4：（中国剩余定理）设是两两互素的正整数，那么对于任意整数，一次同余方程组，必有解，且解可

11、以写为：这里，，以及满足，（即为对模的逆）。例：《孙子算经》里的下卷第26题，是一个闻名世界的数学问题。这问题有人称它为“孙子问题”：“...今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”我们把这个问题再翻译成数学问题，就变成：“寻找x，使得x≡2（mod3），x≡3（mod5），x≡2（mod7）。”现在假定“孙子问题”一般的情形：求x使得x≡r1（mod3）            x≡r2（mod5）         x≡r3（mod7）               由于模3，5，7是两两互素，所以它们的最小公倍数（3，5，7）=3×5×7＝3×35=5×21=7

12、×15＝105因为 35×2≡1（mod3）21×1≡1（mod5）15×1≡1（mod7）因此由同余的可乘性我们得70r1≡r1（mod3）21r1≡r2（mod5）15r1≡r3（mod7）于是我们有70r1＋21r2＋15r3≡70r1≡r1（mod3）70r1+21r2＋15r3≡21r2≡r2（mod5）70r1+21r2＋15r3≡15r3≡r3（mod7）因此同余式组（I）的解是满足下面同余式组的整数值x：x≡70r1＋21r2＋15r3（mod3）x≡70r1＋21r2＋15r3（mod5）                  （2）x≡70r1＋21r2＋15r3（mod7）

13、由于x－（70r1＋21r2＋15r3）是3，5，7的倍数，它也会是（3，5，7）＝105的倍数。故（2）的解同样是和x≡70r1＋21r2＋15r3（mod105）一样。现在回过头看“孙子问题”，r1=2，r2=3，r3=2。由算经的前半段解法是这样：x=70×2＋21×3＋15×2-2×105＝23...中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。以上介绍的只是