更新时间:2023-02-07 17:05
同余式是数论的基本概念之一,设m是给定的一个正整数,a、b是整数,若满足m|(a-b),则称a与b对模m同余,记为a≡b(mod m),或记为a≡b(m)。这个式子称为模m的同余式,若m∤ (a-b),则称a、b对模m不同余,同余概念又常表达为:
一个整数a被m除时,得到商 和唯一的一个余数r,另一个整数b也被m除时,得到商 ,得到的唯一余数r也是,即(其中 )
那么我们说a与b对于模m,有同一个余数r,写成
可以简略地读作:对于模m,a和b同余,其中mod是英文模module的缩写。
(1)同余式可以逐项相加。
若 ,则
(2)同余式一边的数可以移到另一边,只要改变符号就可以了。
若 ,则。
(3)同余式的每一边都可以增加或减去模的任意倍数。
若,则。
(4)同余式可以逐项相乘。
若,则。
(5)我们可以将性质(1)(4)推广成以下的情形。
①若则
②若,则
(6)同余式两边的数如有公约数,此公约数又和模互素,那么就可以把两边的数除以这个公约数。
若,且,则。
(7)同余式两边的数和模可以同时乘上一个整数。
若,则。
(8)同余式两边的数和模可以同时被它们任一公约数除。
若,则。
(9)如果同余式对于模m成立,那么它对于m的任意约数相等的模d也成立。
若,则。
(10)如果同余式一边上的数和模能被某个数除尽,则同余式的另一边的数也能被这个数除尽。
若,则。
(11)同余式一边上的数与模的最大公约数,等于另一边上的数与模的最大公约数。
若,则。
在三国两晋南北朝时期的数学著作中,《孙子算经》卷下的“物不知数问题”和《张丘建算经》卷下的“百鸡问题”,是世界著名的数学问题。《孙子算经》三卷,作者不详,约成书于公元400年前后,《张丘建算经》三卷,作者张丘建,清河(今河北清河)人,生平不详,约成书于公元466至485年之间。这两部著作都被收入唐代《十部算经》,立于学官,并流传至今。“物不知数问题”亦称“孙子问题”,大意是:有物不知其数,三个一数余二,五个一数余三,七个一数余二,问该物总数共有多少?这个问题应该求解一次同余组:,答案是。后来,孙子问题成为广泛流传的一种数学游戏,被称为“韩信点兵”等,并且还编有一首“孙子歌”:“三人同行七十稀,五树梅花廿一枝,七子团圆正半月,除百零五便得知”,这首歌诀暗示出问题的解法。但这不是同余式的一般解法。“孙子问题”与古代历法中推算上元积年有关,南宋数学家秦九韶创造“大衍求一术”,完满地解决了这一问题。他所得到的一次同余组解法公式,现被称为“孙子剩余定理”。
“百鸡问题”的大意是:公鸡1只,值钱5文;母鸡1只,值钱3文;小鸡3只,值钱1文。今有100文钱买鸡100只,问可买公鸡、母鸡和小鸡各多少只?此题有三个未知数,仅能列出两个方程,属于不定方程问题。《张丘建算经》给出三组答案,并有一段说明文字。但是由于其中没有具体解法,因而引起种种猜测。对于中国古代如何解不定方程,至今众说纷纭,尚无定论,不定方程问题最早见于《九章算术》方程章的“五家共井”题,但术文简略,暗含限制条件,没有一般解法。北周甄鸾《数术记遗》也收录了百鸡问题,但数据与《张丘建算经》有所不同。该题应有两组答案,但他仅给出一组,并说明这类问题“不用算筹,宜以心计”,即采用试算的办法去解决。南宋杨辉《续古摘奇算法》引述了《辩古根源》(已失传)中的“百橘问题”,该题应有四组答案,书中仅列出一种,是不完全的。直到19世纪,清代数学家才把这种类型的问题和求一术(一次同余组问题)联系起来,获得了比较完善的解法。晚于《九章算术》时代的公元3世纪古希腊数学家丢番图,对不定方程问题进行了深入的研究,取得了非常出色的成果。15世纪中亚数学家阿尔·卡西的“百禽问题”,与“张丘建算经”的“百鸡问题”非常类似,很有可能受到中国数学的影响。