第三章 同 余§1 同余得概念及其基本性质同余性质在算术中得一些应用。一、检查因数得方法1、一整数能被 3(或 9)整除得充分必要条件就是它得十进位数码之与能被3(或 9)整除。证明 只需讨论正整数即可。任取,则 a 可以写成十进位得形式:2、设正整数,则 7(或 11 或 13)|a 得充分必要条件就是 7(或 11 或 13)|证明 因为 7×11×13=1001。例 3 a=5874192 能被 3 与 9 整除。例 4 a=435693 能被 3 整除,但不能被 9 整除。例 5 a=637693 能被 7 整除;a=75312289 能被 13 整除。二、弃九法(验算整数计算结果得方法)例 6 设 a=28997,b=39495,P=ab=1145236415,检查计算就是否正确。解 令 则 (*)若(*)不成立,则 P≠ab,故在本题中,计算不正确。注 (1) 若(*)不成立,则计算不正确;但否命题不成立。(2) 利用同样得方法可以用来验证整数得加、减运算得正确性。§2 剩余类及完全剩余系 推论 m 个整数作成模 m 得一个完全剩余系得充分必要条件就是它们对模 m 两两不同余。例如,下列序列都就是模 m 得完全剩余系:§3 简化剩余系与欧拉函数§4 欧拉定理·费马定理
