初等数论同余论文

题：p为质数，0＜a＜p，证：x≡b*(-1)^(a-1)*(p-1)**(p-a+1)／a! (mod p)是同余式 ax≡b (mod p)的解证：以下≡为便于打字也记成==将x≡b*(-1)^(a-1)*(p-1)**(p-a+1)／a! 代入ax mod p中得：ax=b*(-1)^(a-1)*(p-1)**(p-a+1)／(a-1)! =b*(1-p)**(a-1-p)／(a-1)! mod p==b*1**(a-1)/(a-1)!=b得证。备忘：下面的内容与上题的证明无关。由wilson定理，(p-1)!==-1 mod p

数学上，两个整数除以同一个整数，若得相同余数，则二整数同余（英文：Modular arithmetic；德文：Kongruenz）。同余理论常被用于数论中。最先引用同余的概念与符号者为德国数学家高斯。同余理论是初等数论的重要组成部分，是研究整数问题的重要工具之一，利用同余来论证某些整除性的问题是很简便的。同余是数学竞赛的重要组成部分。

以同余的慨念和同余的性质为基础发展起来的同余理论是初等数论的核心，是数论所特有的思想、概念与方法。

10^10同余（10^3）x（10^3）x（10^3）x10同余6x6x6x4同余1x1x1x3同余-3（mod7）所以为星期五

A为十进制数n=4568^7777的各位数字之和，B为A的各位数字之和，C为B的个位数字之和，C=（）A5B32C9D14先用一个任意的三位数w=100x+10y+z说明一个引理w的各位数字之和是:w1=x+y+可以看到,w==w1mod9于是排除答案C以上说明的是：引理1:数n=a2a1a0,其数字和为S(n),则n==S(n)即9|n-S(n)引理2正整数n的十进制位数:b(n)=1+[lgn]。例如：10的位数是2,lg10=1;99的位数是2,lg99<2由此立即得到引理3:正整数n的十进制表示的各位数字之和S(n)<=9(1+[lgn])。解：记n的各位数字和为S(n)取n=4568^7777A=S(n)<=9*(1+7777*lg4568)<9*(1+7777*4)=9*31109=279981从而B=S(A)<=2+9*5-1=46从而C=S(B)<=4+9-1=12由此可以在四个答案A5B32C9D14中，只有A,C候选。又易见以下各数除以9的余数相等n,A,B,C（数论上讲：n==Amod9,n与A关于除数(模)9同余）显然n==4568^7777==5^7777<>0mod9由此可以排除答案C综上，选A附记：n==4568^7777mod9==5^(7777mod6)mod9==5^1==5这里利用到若（a,m）=1,m不整除r,则a^rmodm==a^(rmodφ(m))modm,其中φ(m)为m的欧拉函数,即m的既约剩余系中的同余类的个数，也就是小于m的正整数中与m互质的数的个数。φ(9)=如果不利用欧拉函数，仅利用同余知识，可以写成：n==4568^7777mod9==5^7777==125^2592*5==(-1)^2592*5==5mod9