欧拉函数公式及其证明(4页).doc
《欧拉函数公式及其证明(4页).doc》由会员分享,可在线阅读,更多相关《欧拉函数公式及其证明(4页).doc(4页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、-欧拉函数公式及其证明-第 4 页欧拉函数 :欧拉函数是数论中很重要的一个函数,欧拉函数是指:对于一个正整数 n ,小于 n 且和 n 互质的正整数(包括 1)的个数,记作 (n) 。 完全余数集合:定义小于 n 且和 n 互质的数构成的集合为 Zn ,称呼这个集合为 n 的完全余数集合。 显然 |Zn| (n) 。有关性质:对于素数 p ,(p) = p -1 。对于两个不同素数 p, q ,它们的乘积 n = p * q 满足 (n) = (p -1) * (q -1) 。这是因为 Zn = 1, 2, 3, . , n - 1 - p, 2p, . , (q - 1) * p - q,
2、2q, . , (p - 1) * q , 则 (n) = (n - 1) - (q - 1) - (p - 1) = (p -1) * (q -1) (p) * (q) 。欧拉定理 :对于互质的正整数 a 和 n ,有 a(n) 1 mod n 。证明:( 1 ) 令 Zn = x1, x2, ., x(n) , S = a * x1 mod n, a * x2 mod n, . , a * x(n) mod n , 则 Zn = S 。 因为 a 与 n 互质, xi (1 i (n) 与 n 互质, 所以 a * xi 与 n 互质,所以 a * xi mod n Zn 。 若 i j
3、, 那么 xi xj,且由 a, n互质可得 a * xi mod n a * xj mod n (消去律)。( 2 ) a(n) * x1 * x2 *. * x(n) mod n (a * x1) * (a * x2) * . * (a * x(n) mod n (a * x1 mod n) * (a * x2 mod n) * . * (a * x(n) mod n) mod n x1 * x2 * . * x(n) mod n 对比等式的左右两端,因为 xi (1 i (n) 与 n 互质,所以 a(n) 1 mod n (消去律)。注:消去律:如果 gcd(c,p) = 1 ,则 a
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 函数 公式 及其 证明
限制150内