同余 - DGSO百科

同余 百科内容来自于: 百度百科

数论中的重要概念。给定一个正整数m,如果两个整数a和b满足a-b能被m整除,即m|(a-b),那么就称整数a与b对模m同余,记作a≡b(mod m)。对模m同余是整数的一个等价关系。

理论背景

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

同余符号

两个整数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去除,余数相同。
【证明】
充分性: m|(a-b)——> a≡b(mod m)
设a=mq1+r1,b=mq2+r2
且0≤r1,r2<m
∵ m|(a-b)
又a-b=m(q1-q2)+(r1-r2).
∴必有常数n使得(r1-r2)=mn
则有m|(r1-r2).
∵0≤r1,r2<m,
∴0≤|r1-r2|<m
∴r1-r2=0
即r1=r2.
故a≡b(mod m).
必要性:a≡b(mod m)——>m|(a-b)
设a,b用m去除余数为r,
即a=mq1+r,b=mq2+r.
∵a-b=m(q1-q2)
∴m|(a-b).

性质

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+-c≡b+-d (mod m)
5 同余式相乘 若a≡b (mod m),c≡d(mod m),则ac≡bd (mod m)
证明】上述性质很容易证明,下面仅证明(3).
∵a≡b(mod m)∴m|(a-b) 同理m|(b-c),
∴m|[(a-b)+(b-c)]∴m|(a-c).
故a≡c(mod m).
4线性运算如果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)
5除法若ac ≡ bc (mod m) c≠0 则 a≡ b (mod m/gcd(c,m)) 其中gcd(c,m)表示c,m的最大公约数
特殊地 ,gcd(c,m)=1 则a ≡ b (mod m)
6 幂运算如果a ≡ b (mod m),那么a^n ≡ b^n (mod m)
7 若a ≡ b (mod m),n|m,则 a ≡ b (mod n)
8 若a ≡ b (mod mi) (i=1,2...n) 则 a ≡ b (mod [m1,m2,...mn]) 其中[m1,m2,...mn]表示m1,m2,...mn的最小公倍数
设a,m∈N,(a,m)=1,则a^(φ(m))≡1(mod m)
(注:φ(m)指模m的简系个数, φ(m)=m-1, 如果m是素数;φ(m=q1^r1 * q2^r2 * ...*qi^ri)=m (1-1/q1)(1-1/q2)...(1-1/qi))
推论:费马小定理: 若p为质数,则a^p ≡ a (mod p) 即a^(p-1) ≡ 1 (mod p)
(但是当p|a时不等价
10 中国剩余定理
设整数m1,m2,m3,......,mn 两两互素,令m=m1m2m3m4m5...mn(mi的连乘)。则对于任意的J在(1,n)整数,下列联立的同余式有解:
{xj≡1(mod mj)
{xj≡0(mod mi) i不等于j
令x为从1到najxj的和,则x适合下列联立同余式
x≡aj(mod mj), j=1,2,3,.....,n
另:求自然数a的个位数字,就是求a与哪一个一位数对于模10同余

相关定理

一次同余式孙子定理 同余式的求解中,一次同余式是最基本的。设整系数 n次( n>0)多项式 ƒ( x)= αn x+…+ α1 x+ α0,m是一个正整数且不能整除 αn,则
(1)叫做模m的 n同余式。如果整数 α是(1)的解且 αα┡(mod m),那么 α┡也是(1)的解,因此,(1)的不同解是指满足(1)的模 m互不同余的数。对于一次同余式 α xb(mod m)有解的充分必要条件是( α,m)│ b),若有解则有( α,m)个解。一次同余式组是指
。 (2)
在中国古代《孙子算经》中,对某些具体的一次同余式组已有解法,把这一解法加以推广,就是著名的孙子剩余定理:设m 1, m 2,…, m kk个两两互素的正整数
,则同余式组(2)的解是。式中,孙子剩余定理又被称之为中国剩余定理,是数论中一个重要的定理,除了数论本身,数学的许多其他分支以及一些应用学科都要用到它。例如,设m=m1m2…mk,m1, m2,…,mk两两互素,利用孙子剩余定理可将同余式(1)的求解问题化为同余式组 ƒ( x)≡0(mod mi)( i=1,2,…, k)的求解问题,于是就只需要研究(1)中m是素数方幂的情形了。又如,可将0≤ x<m中的一切整数表示,这叫做模系数记数法,这里m=m 1m 2…m k,m 1, m 2, …, m k两两互素,而x表示 x模m i的最小非负剩余。
如果已知 x的模系数记数法,就可用孙子定理找出 x。这个记数法的优点是加法和乘法无须进位,它在计算机方面有应用。
素数为模的同余式 关于素数为模的同余式,1770年,J.-L.拉格朗日证明了如下定理:设 p是素数,那么模 pn次同余式的解数不大于 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.沃斯顿霍姆证明的。
ƒ( x1, x2,…, xn)是 n元整系数多项式, p是一个奇素数,对于同余式 ƒ( x 1, x 2,…, x n) ≡0(mod p)的解( x 1, x 2,…, x n)(0≤ xj< p, j=1,2,…, n)的个数 N的研究,是数论的重要课题之一。
早在1801年,C.F.高斯就研究了同余式 α x- b) y≡1(mod p)的解的个数,这里 p≡1(mod 3)和同余式 α x- b) y≡1(mod p)的解的个数,这里 p≡1(mod 4)。
ƒ( x)模 p无重因式,1924年,E.阿廷猜想同余式 yƒ( x)(mod p),在 ƒ( x)的次数为3和4时, N分别满,1936年,H.哈塞证明了这一猜想,并且还证明了对于一般含 q个元的有限域,把以上两式中 p换成 q,也是对的。1948年,韦伊对于一般的 ƒ( x, y)=0在有限域上得到类似的结果, 他猜想对于 ƒ( x 1, x 2,…, x n)=0也有类似的结果。1973年,P.德利涅证明了韦伊猜想。他的杰出工作获得了1978年的国际数学家会议的费尔兹奖。