数论中的重要概念。给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(mod m)。对模m同余是整数的一个等价关系。1
理论背景数学上,两个整数除以同一个整数,若得相同余数,则二整数同余(英文: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猜想的线索。2
同余符号两个整数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是整数,如果(a-b)|m,则称a与b关于模m同余,记作a≡b(mod m),读作a与b对模m同余。
显然,有如下事实
(1)若a≡0(mod m),则a|m;
(2)a≡b(mod m)等价于a与b分别用m去除,余数相同。
证明充分性:m|(a-b)→a≡b(mod m)。
设a=mq1+r1,b=mq2+r2,
且0≤r1,r2