1、第 7讲 数论基础整除、素数、最大公约数，欧几里德算法整除、素数、最大公约数，欧几里德算法模运算、同余、乘法逆元素、扩展的欧几里德算法模运算、同余、乘法逆元素、扩展的欧几里德算法中国剩余定理、费马小定理、欧拉定理中国剩余定理、费马小定理、欧拉定理模的幂、模模的幂、模 n逆矩阵、模逆矩阵、模 n平方根平方根有限域理论有限域理论素数判定和因数分解素数判定和因数分解第 7讲 数论基础一、整除、素数、最大公约数，欧几里德算法一、整除、素数、最大公约数，欧几里德算法整除整除举例举例 ： 3|15， -15|601.定义： 设整数 a和 b,且 a 0，如果存在整数 k使得 b=ak，那么就说 a整除 b
2、（或 b能被 a整除） ，记作 a|b，或者说b是 a的倍数。 2.整除的基本性质 ( N 整数集 )(1) a(a0), a|0,a|a (同理 b N,1|b)(2) b|a, cb|ca(3) a|b, b|c a|c.（传递性）(4) a|b, a|c a|(xb+yc) (x,yN)(5) b|a 且 a0 |b|a|(6) cb|ca, b|a整除整除性质一性质一 ：对所有整数：对所有整数 a(a0) ， a|0和和 a|a成立；同成立；同理，对任意整数理，对任意整数 b， 1|b成立。成立。性质二性质二 ：如果：如果 a|b且且 b|c，则，则 a|c成立。成立。证明证明 ：显然
3、成立，证明略：显然成立，证明略证明证明 ：设存在：设存在 k和和 l使得使得 b=ak， c=bl成立，因此成立，因此c=(kl)a，所以，所以 a|c。整除整除性质三性质三 ：如果：如果 a|b且且 a|c，则对所有的整数，则对所有的整数 s和和 t，a|(sb+tc)成立。成立。证明证明 ：设：设 b=ak1， c=ak2，那么，那么 sb+tc=a(sk1+tk2)，所以所以 a|c。整除整除练习练习Q: 下面哪个是对的下面哪个是对的 ?77 | 77 | 7724 | 240 | 2424 | 0素数素数什么是素数？什么是素数？素数是这样一种数：比素数是这样一种数：比 1大，其因子只有
4、大，其因子只有 1和它本和它本身，没有其它数可以整除它。身，没有其它数可以整除它。2是一个素数，其它的素数诸如是一个素数，其它的素数诸如 73， 2521，2365347734339和和 2756839-1等。等。密码学，特别是公开密钥密码常用大的素数（密码学，特别是公开密钥密码常用大的素数（ 512位甚至更长）。位甚至更长）。素数素数1.定义：一个大于 1的整数 p， 只能被 1或者是它本身整除 ,而不能被其他整数整除，则称整数为素数 (prime number)，否则就叫做合数 (composite)。eg 素数（ 2， 3， 5， 7， 11， 13等）合数（ 4， 6， 8， 9， 12等）
