1、 数论入门 2008-03-31 西安电子科技大学计算机学院 21 素数n 数论主要关心的是素数n 整数 p 1是素数，当且仅当它只有因子 1和 p。q 素数不能写作其它数的乘积 q 1是素数，但一般对它没兴趣 n 例如： 2,3,5,7是素数， 4,6,8,9,10 不是素数n 200以内的素数 : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 1
2、97 199 2008-03-31 西安电子科技大学计算机学院 32008-03-31 西安电子科技大学计算机学院 4素数的个数2008-03-31 西安电子科技大学计算机学院 5素因子分解n 算数基本定理：任意整数 a 1 都可以唯一地因子分解为a = p1a1p2a2p tat ，其中， pi 均是素数，且p10q 如 . 91 = 7 x 13 ; 3600 = 24 x 32 x 52 n 确定一个大数的素因子分解不是一件容易的事2008-03-31 西安电子科技大学计算机学院 6互素和最大公因子n 两个数 a, b 互素，如果它们没有除 1以外的公因子 q 如 ( 8, 15 ) =
3、 1 n 最大公因子q 如 : 300 = 22 x 31 x 52 18 = 21 x 32 因此 GCD( 18, 300 ) = 21 x 31 x 50 = 62008-03-31 西安电子科技大学计算机学院 72 Fermat定理和 Euler定理n ap-1 1 ( mod p)qp是素数， gcd( a, p ) = 1n Fermat小定理qap p (mod p)qp是素数， a是任意整数q 在公钥密码中很有用Fermat 定理定理2008-03-31 西安电子科技大学计算机学院 8n 小于 n且与 n互素的正整数的个数 如 n = 10, 0, 1, 2, 3, 4, 5,
4、 6, 7, 8, 9 ， 1, 3, 7, 9 (10) = 4n 素数 p (p) = p-1 n 素数 p, q，有 (pq) = (p-1) x (q-1) n 如：(37) = 36(21) = (31) x (71) = 2 x 6 = 12n 约定： (1) = 1Euler函数函数 (n)2008-03-31 西安电子科技大学计算机学院 9n 定 理：设 n = p1e1 p2e2 p rer， pi pj,pi为素数， ei1,则(n) = n (1-p1-1) (1-p2-1)(1-p r-1)例如： 12 = 22 * 3(12) = 12 * (1-2-1) * (1-3-1) = 42008-03-31 西安电子科技大学计算机学院 10
