文档介绍：同余
§
定义1 给定一个正整数,如果,则称整数对模同余,记作;如果,则称整数对模不同余,记作。
从定义可以看出,任意的两个整数,要么,要么。结合整除的性质,我们很容易得到同余的两个等价定义:
(1)整数对模同余的充要条件是存在一个整数使得;
(2)整数对模同余的充要条件是用去除整数和所得的最小非负余数相同。
在同余式中,若,则称是对模的最小非负剩余,一般用来表示;若,则称是对模的最小正剩余;若,,则称是对模的绝对值最小剩余。
从关系的角度出发,我们很容易证明同余是一种等价关系,即同余满足如下性质:
性质1 (1)自反性:;
(2)对称性:;
(3)传递性:
。
同余其实就是整除的一种符号表示,因此我们在第一章中了解的整除的一些基本性质都可以用同余符号简单地表示。
性质2 (1) 若,,则
,
特别地,对于任意一个整数,都有
,;
(2)若,,则
;
(3)若,的公因数,则;
(4)若,,,则;
(5)若,是的最大公因数,则,进一步,若,则有;
(6)若,则,进一步,若是一个整系数多项式(即系数
是整数,其中),则;
(7)同余式组同时成立的充要条件是
;
(8)。
利用上述关于同余的一些基本性质,我们可以得到检查因数的两个方法:
例1 证明:一个整数能被3或9整除的充要条件是它的十进位数码的和能被3或9整除。
证明:设是一个正整数。把写成十进位数的形式:
。
因为,所以,由此可知,当且仅当,对于9的情形同理可证。如:,,,所以3是的因数,9不是的因数。
例2 设
证明:能被7(或11,或13)整除的充要条件是7(或
11,或13)整除。
证明:因为,即,所以,即有
,于是当且仅当,对于11、13的情形同理可证。
因为,所以在判断一个整数是否被11整除时用百进制更简单。
下面我们介绍一个很有名的称作弃九法的方法,它利用同余的性质来验算整数计算结果是否错误。这个方法对于加、减、乘都适用,为了简便,我们只给出普通乘法的证明。假设我们由普通乘法运算求出整数的乘积为,并且设
。
。
。
如果有
则所计算的结果是错误的。
按照例1,,,,由同余的性质当然可以得到
,所以,若,则。
例3 设,,如果按照普通乘法计算得到的乘积是,那么按照上面的方法,,,但是,所以计算有误。
从上面的证明我们可以看出这种方法有一个缺陷,当使用弃九法时,得到的结果虽然是,也不能完全肯定原计算是正确的。如在上面例子中,如果有人计算出来的结果为4540485362,那么用弃九法得到,而并未检查出错误来,实际的乘积结果为4540485326。
2005年7月26日是星期二,问此天后第天是星期几?
解依题意,我们需要求,即整数模7的最小非负剩余。
因为,所以
因此,第天是星期四。
现在我们利用同余的理论来计算某一特定的日子是星期几。例如,香港回归日1997年7月1日是星期几,或者中华人民共和国成立日是星期几?如果一年的天数可被
7整除,那么所有的日期在每一年中总有相同的星期数,这样日历的编制将大大简化。但是,目前一年的天数是,而闰年的天数是,这表明,在平年一个给定日期的星期数在下一年要加1,碰到闰年这一规律就被破坏了。值得注意的是,目前国际通用的公历是教皇格里高利十三实行的。当时他召集了很多学者和僧侣讨论历法改革问题,决定采用业余天文学家利里奥的方案,每四百年去掉三个闰日,那些世纪数不能被4整除的世纪年不再算作闰年。
下面我们给出一个方便的计算公式,为此规定0代表星期日,1代表星期一,2代表星期二,3代表星期三,4代表星期四,5代表星期五,6代表星期六。注意到闰年所加的一天不在一年的开头,也不在一年的末尾,而是在2月的29日,因此我们可以做如下处理:约定3月为第一个月,第二年的2月作为第十二个月。如1997年7月1日要写成“1997年5月1日”,1997年1月1日要写成“1996年11月1日”。
假定有一个具体的日期(注意如下的公式和公式的证明都是经过处理后的时间):第年月日。令(即为100除的最小非负余数),,如果用表示这一日期的星期数,则有如下计算公式:
如1997年7月1日要写成“1997年5月1日”,代入上式计算可得,因此1997年7月1日是星期二。
上述公式的证明:首先任取一年如2000年作为开始的一年,并且把这一年的1月1日(实际时间为3月1日)的星期数记为,下面来求第年1月1日的星期数。注意到平年的天数为365,且,每过一个平年,星期数将增加1,若不考虑闰年,则相应的第年1月1日的星期数为
闰年的天数为366,注意到闰年每4年一次,通常年数被4整除时是闰年,世纪年通常不是闰年,但当世纪数可被4整除时,第年仍然