竞赛数论基础.ppt

数论基础 A 1素数与互素A 2同余与模运算A 3欧拉定理A 4几个有用的算法 授课内容 A 1素数与互素 1整除 定义1 1设a b为整数 a 0 若有一整数q 使得b aq 则称a是b的因数 b是a的倍数 并称a整除b 记为a b 可形式地表示为 a b q b aq 若a不能整除b 记为a b 若b aq 而a既非正负b又非正负1 则称a是b的真因数 1整除 关于整除 显然有下列定理 定理1 1 对所有a 1 a 对所有a a 0 对所有a a a 若a b且b c 则a c 若a b 则对任意的c 0 有ac bc 若ac bc且c 0 则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 b a b 2素数和合数 在正整数中 1只能被它本身整除 任何大于1的整数都至少能被1和它本身整除 定义2 1一个大于1且只能被1和它本身整除的整数 称为素数 否则 称为合数 由该定义可知 正整数集合可分三类 素数 合数和1 素数常用p或p1 p2 来表示 2素数和合数 定义2 2若正整数a有一因数b 而b又是素数 则称b为a的素因数 例 12 3 4 其中3是12的素因数 而4则不是 素数有多少 公元前三世纪 古希腊数学家欧几里德Euclid就证明了素数有无穷多个 2素数和合数 素数的一些基本结论 素数有无穷多个素数的整除性素数定理算术基本定理 有限分解和唯一分解 3最大公因数和最小公倍数 定义3 1设al a2 an和d都是正整数 n 2 若d ai 1 i n 则称d是al a2 an 的公因数 在公因数中最大的那一个数 称为al a2 an的最大公因数 记为gcd al a2 an greatestcommondivisor 或者 al a2 an 若gcd al a2 an 1 称al a2 an是互素的 3最大公因数和最小公倍数 在互素的正整数中 不一定有素数 例如 25 36 1 但25和36都不是素数而是合数 在个数不少于3个的互素正整数中 不一定是每二个正整数都是互素的 例 6 10 15 1 但 6 10 2 6 15 3 10 15 5 3最大公因数和最小公倍数 最大公因子有下列性质 任何不全为0的两个整数的最大公因子存在且唯一设整数a与b不全为0 则存在整数x和y 使得ax by gcd a b 特别地 如果a b互素 则有ax by 1若gcd a b d 则gcd a d b d 1若gcd a x gcd b x 1 那么gcd ab x 1若c ab gcd b c 1 则c a 3最大公因数和最小公倍数 定义3 2设a1 a2 an和m都是正整数 n 2 若ai m 1 i n 则称m是a1 a2 an的公倍数 在a1 a2 an所有公倍数中最小的那一个 称为a1 a2 an的最小公倍数 记为lcm a1 a2 an leastcommonmultipler 或者 a1 a2 an A 2同余与模运算 同余是数论中一个基本概念 它的引人简化了数论中的许多问题同余的很多性质和 等于 很类似 1带余除法 若a b是二个正整数 b 0 则唯一存在二个整数k和r 使得下式成立 a bk r 0 r b 分别称k和r为a除以b 或者b除a 的商和余数 还可表示为 a a b b a modb 例A 1参见教材p144 2整数同余与模运算 定义2 1给定一正整数m 若用m去除两个整数a和b所得余数相同 则称a与b模m同余 记作a b modm 若余数不同 则称a与b模m不同余 记作a b modm m称为模数 a modm 称为a模m的余数 显然 a 0 modm iffm a a b modm a km bm a b例A 2 参见教材p145 2整数同余与模运算 模n同余类 剩余类 任何整数a除以正整数n的余数一定在集合 0 1 2 n 1 中 所有整数根据模n同余关系可以分成n个集合 每一个集合中的整数模n同余 这样的集合称为模n同余类 剩余类 思考 从同余类的记法可以看出 它是否与代表元的选取有关 模n的完全剩余系从每一个模n同余类中取一个数为代表 形成一个集合 此集合称为模n的完全剩余系 记为ZnZn最简单表示就是集合 0 1 2 n 1 即Zn 0 1 2 n 1 2整数同余与模运算 模运算的性质 自反性 a a modm 对称性 若a b modm 则b a modm 传递性 若a b modm b c modm 则 a c modm 可见 同余关系是等价关系 若a b modm c d modm 则 a c b d modm ac bd modm 模运算具有普通运算的代数性质 可交换 可结合 可分配 amodn bmodn modn a b modn amodn bmodn modn a b modn amodn X bmodn modn axb modn aXb modn aXcmodn modn ax b c modn 加法消去律 如果a b a c modn 则b c modn 乘法消去律 如果ab ac modn 且gcd a n 1 则b c modn 如果ab dc modn 且a d modn 以及gcd a n 1 则b c modn 例A 3参见教材P145 指数模运算可以变成模指数运算 从而使运算得以简化 例如887mod187 884mod187 x 882mod187 x 88mod187 mod187882mod187 7744mod187 77884mod187 882mod187 x 882mod187 mod187 77x77 mod187 132887mod187 132X77X88 mod187 11例A 4参见教材P146 消去律的条件逆元的概念加法逆元 设a n Z且n 1 如果存在b Z使得a b 0 modn 则称a b为互为模n的加法逆元 也称负元 记为b a modn 乘法逆元 设a n Z且n 1 如果存在b Z使得ab 1 modn 则称a b为互为模n的乘法逆元 记为b a 1 modn 逆元的存在性加法逆元总存在 例如n a乘法逆元存在的充要条件是a与n互素时 A 3欧拉定理 1欧拉函数 对于正整数n n 定义为小于n且与n互质的正整数的个数 例如 6 2 这是因为小于6且与6互质的数有1和5共两个数再如 7 6 这是因为互质数有1 2 3 4 5 6共6个 如果n为素数 则 n n 1如果gcd m n 1 则 mn m n 2欧拉定理 费尔马定理 欧拉定理实际