4.3 同余
本章目录 · 1 节
本章导读
定义4.3.1:正整数 为模数,整数 若满足 ,称 与 模 同余,记 ;否则记 。等价条件是两数除以 的非负余数相同,或者存在整数 使 。例如 、、,而14与21模6不同余。模数必须为正,不能把模0代入本节定义。
命题4.3.1:同余关系自反、对称、传递。分别因为 、、,均保持被 整除。若多个数依次同余,可以连写同余式,但每一步应始终使用同一模数。
命题4.3.2概括运算规则:(1)若 ,则 、,并有 ();(2)若正整数 ,模 同余推出模 同余;(3)正整数 下, 当且仅当 ;(4)若 ,则 当且仅当 。前几项把差式写为 的倍数即可证明;消去因子 时则要用贝祖等式,或乘 的模逆元。
同余中不能随意约分。例如 ,却没有 ,因为2与6不互素。若 ,一般正确结论是 当且仅当 ,约掉公因子时模数也相应缩小。
整数的模 等价类记 ,商集记 。在同一个模数下定义 、;同余运算规则保证更换代表元不会改变结果,因此这些是良定义的运算。不同模数的等价类及运算不能混用。
【例4.3.1】列出 的全部元素和加法、乘法表。
解:元素为 ,其中 。按0到4排列行、列,表中每个数均代表对应等价类:
例如 ,;两次恰好相同是此例的数值结果,不是加法等于乘法的一般规则。
【例4.3.2】求 的个位数字。
解:,,所以 。个位数字为7,不必计算整个巨大整数。
【例4.3.3】用同余计算公历日期的星期数,约定0到6依次表示星期日到星期六。
解:公历闰年规则是年份被4整除,但世纪年还必须被400整除。因此1900、2100不是闰年,2000、2400是闰年。把3月看作计算年的第1月,次年1、2月看作第11、12月,定义 ,,并把 ,其中 。
以3月1日为起点,跨过一个平年星期增加1,跨过闰年再增加1;扣去非闰的世纪年后,教材公式为
从计算年第1月到第 月1日,除每月30天外的累计补偿 按表4.3.1依次为 (对应 ),可统一写成 。再加日期偏移 ,得到
最后把余数规范化为0到6。1949年10月1日取 ,得 ,为星期六;1945年8月15日取 ,得 ,为星期三。计算前应先确认日期有效,例如非闰年的2月29日不能当成正常输入。对历史上尚未改用公历的地区和日期,本式只能理解为外推公历,不自动表示当时实际采用的历法。
