開啟主選單
求真百科
搜尋
檢視 同余 的原始碼
←
同余
由於下列原因,您沒有權限進行 編輯此頁面 的動作:
您請求的操作只有這個群組的使用者能使用:
用戶
您可以檢視並複製此頁面的原始碼。
{| class="wikitable" align="right" |- | style="background: #66CCFF" align= center| '''<big>同余</big> ''' |- |<center><img src="https://img14.360buyimg.com/pop/jfs/t1/167226/5/31272/37113/6344a207E41ec5d11/d5278265ce32f028.jpg/400/fill/I0JBQkFCMA==/dissolve/70" width="250" ></center> |- | style="background: #66CCFF" align= center| |- | align= light| |} '''同余''',数论中的重要概念。给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(mod m)。对模m同余是整数的一个等价关系。 同余关系: 同余:如果a和b除以c的余数相同,就说a和b关于模c同余,记作a≡b(mod c)。 如果两个数a和b的差能够被m整除,那么就说a和b对模数m同余(关于m同余)。 比如,28-13=15除以5正好除尽,我们就说28和13对于模数5同于,因为15是5的整数倍。它的另外一层含义就是说:28和13除以5的余数相同。a和b对m同余,我们记作a≡b(mod m)。比如,28与13对5同余可以写作28≡13(mod 5)。 同余关系是一种等价关系。 1.自反性:一个数永远和自己本身同余 2.对称性:a和b同余,b和a也就同余 3.传递性:a和b同余,b和c也同余,可以推出a和c也是同余的 同余运算中还有一些稍微复杂的性质。比如,同于运算和整数加减法一样满足“等量+等量,其和不变”。<ref>[https://blog.csdn.net/shiyongyang/article/details/78108895 同余详解入门],csdn , </ref> ==理论背景== 数学上,两个整数除以同一个整数,若得相同余数,则二整数同余(英文:Modular arithmetic,德文:Kongruenz)。同余理论常被用于数论中。最先引用同余的概念与符号者为德国数学家高斯。同余理论是初等数论的重要组成部分,是研究整数问题的重要工具之一,利用同余来论证某些整除性的问题是很简便的。同余是数学竞赛的重要组成部分。 公元972年,在一份阿拉伯手稿中,提出了这样一个问题:一个正整数n何时能成为一个由三个有理平方数形成的等差数列的公差,也就是说x-n,x,x+n都是平方数。十三世纪,意大利数学家斐波那契指出5和7是同余数,他也猜想1、2、3不是同余数,但未能给出证明。直到1659年,法国大数学家费尔马运用他自己发明的无穷下降法证明了1、2、3不是同余数。十八世纪,大数学家欧拉首次证明了7是同余数。1952年,Heegner证明了任意模8余5、7的素数和任意模4余3的素数的两倍均为同余数。2000年,美国克雷数学研究所公布了千禧年七大数学难题,每破解其中一个难题者将获得100万美元的奖金。其中就有著名的BSD猜想(全称Birch and Swinnerton-Dyer猜想),而这个猜想与同余数问题有紧密的联系。2012年,田野证明了存在无穷多个具有任意指定素因子个数的同余数,这是在同余数问题上的一个根本性突破,也首次给出了解决BSD猜想的线索。 ==同余符号== 两个整数a、b,若它们除以整数m所得的余数相等,则称a与b对于模m同余或a同余于b模m。 记作:a≡b (mod m), 读作:a同余于b模m,或读作a与b对模m同余,例如26≡2(mod 12)。 ==定义== 设m是大于1的正整数,a、b是整数,如果m|(a-b),则称a与b关于模m同余,记作a≡b(mod m),读作a与b对模m同余。 显然,有如下事实 (1)若a≡0(mod m),则m|a; (2)a≡b(mod m)等价于a与b分别用m去除,余数相同。 ==证明== 充分性: 设a=mq1+r1,b=mq2+r2,0<=r1,r2<m ∵ m|(a-b),a-b=m(q1-q2)+(r1-r2). 则有m|(r1-r2). ∵0<=r1,r2<m ∴0<=|r1-r2|<m 又∵m|(r1-r2) 即r1-r2=0 ∴r1=r2. ==性质== 1.反身性:a≡a (mod m); 2.对称性:若a≡b(mod m),则b≡a (mod m); 3.传递性:若a≡b(mod m),b≡c(mod m),则a≡c(mod m); 4.同余式相加:若a≡b(mod m),c≡d(mod m),则a d(mod m); 5.同余式相乘:若a≡b(mod m),c≡d(mod m),则ac≡bd(mod m)。 证明: ∵a≡b(mod m)∴m|(a-b) 同理m|(b-c), ∴m|[(a-b)+(b-c)]∴m|(a-c). 故a≡c(mod m). 6.线性运算:如果a ≡ b (mod m),c ≡ d (mod m),那么 (1)a ± c ≡ b ± d (mod m); (2)a * c ≡ b * d (mod m)。 证明: (1)∵a≡b(mod m), ∴m|(a-b) 同理 m|(c-d) ∴m|[(a-b)±(c-d)] ∴m|[(a±c)-(b±d)] ∴a ± c ≡ b ± d (mod m) (2)∵ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d) 又 m|(a-b) , m|(c-d) ∴m|(ac-bd) ∴a * c ≡ b * d (mod m) 7.除法:若 ,其中gcd(c,m)表示c和m的最大公约数, 特殊地, ; 8.幂运算:如果 ; 9.若 ; 10.若 表示m1,m2,...mn的最小公倍数。 ==相关定理== 1.欧拉定理:设a,m∈N,(a,m)=1,则 (注:φ(m)指模m的简系个数, φ(m)=m-1,如果m是素数; 2.费马小定理: 若p为质数,则 (但是当p|a时不等价)。 3.中国剩余定理(孙子定理): 设整数 (mi的连乘)。则对于任意的j在(1,n)整数,下列联立的同余式有解: 令x为从1到n,ajxj的和,则x适合下列联立同余式, 另:求自然数a的个位数字,就是求a与哪一个一位数对于模10同余。 一次同余式和孙子定理同余式的求解中,一次同余式是最基本的。设整系数n次(n>0)多项式 。 (2) 两两互素,而x表示x模mi的最小非负剩余。 如果已知x的模系数记数法,就可用孙子定理找出x。这个记数法的优点是加法和乘法无须进位,它在计算机方面有应用。 素数为模的同余式关于素数为模的同余式,1770年,J.-L.拉格朗日证明了如下定理:设p是素数,那么模 p的n次同余式的解数不大于 n(重解也计算在内)。人们称之为拉格朗日定理。由此立即可以得威尔森定理:如果 p是素数,那么(p-1)!+1≡0(mod p)。因为x-1≡0(mod p)有p-1个解1,…,p-1,故由拉格朗日定理可得 将x=0代入上式得-1≡(-1)(p-1)!(mod p),这就证明了威尔森定理。威尔森定理的逆定理也是成立的,可用反证法简单证出。用拉格朗日定理还可证明:当p≥5是一个素数时,则有同余。这个定理是1862年,由J.沃斯顿霍姆证明的。 设 的个数N的研究,是数论的重要课题之一。 早在1801年,C.F.高斯就研究了同余式 。 设ƒ(x)模 p无重因式,1924年,E.阿廷猜想同余式 也有类似的结果。1973年,P.德利涅证明了韦伊猜想。他的杰出工作获得了1978年的国际数学家会议的费尔兹奖。 == 参考来源 == {{reflist}} [[Category: 310 數學總論]]
此頁面使用了以下模板:
Template:Main other
(
檢視原始碼
)
Template:Reflist
(
檢視原始碼
)
模块:Check for unknown parameters
(
檢視原始碼
)
返回「
同余
」頁面