数 论 基 础 n A.1 素数与互素 n A.2 同余与模运算 n A.3 欧拉定理 n A.4 几个有用的算法 授 课 内容 A.1 素数与互素 1 整除 定 义 1.1 设 a,b为 整数， a0. 若有一整数 q, 使得 b = aq, 则 称 a是 b的因数 ,b是 a 的倍数 ; 并称 a整除 b, 记为 a|b, 可形式 地表示 为 : a|b:=(q)(b=aq) n 若 a不能整除 b，记为 ab. n 若 b=aq,而 a既非正 负 b又非正 负 1,则 称 a 是 b的 真因数 . 1 整除 n 关于整除， 显 然有下列定理： 定理 1.1 对 所有 a, 1|a. 对 所有 a, a|0. 对 所有 a, a|a. 若 a|b且 b|c, 则 a|c. 若 a|b, 则对 任意的 c0, 有 ac|bc. 若 ac|bc且 c0, 则 a|b. 1 整除 若 a | b且 a|c,则对 任意的 m,n,有 a|(bm+cn). 若 a|b, 则 b=0或 |a|b|,其中 |a|是 a的 绝对值 . 若 a|b, 则 (-a)|b, a|(-b),(-a)|(-
