离散数学ii（李占山）5-4秦九韶定理euler函数.ppt

5 4秦九韶定理Euler函数 5 4 1一次同余式组秦九韶定理 定理5 4 1设 m1 m2 为m1 m2的最低公倍数 则同余式组x a1 modm1 x a2 modm2 1 在mod m1 m2 下有唯一解的充要条件为 m1 m2 a1 a2 2 证明 必要性 记m1 m2的最高公因数和最低公倍数分别为d m 即d m1 m2 m m1 m2 若 1 有解x0 则x0 a1 modd x0 a2 modd 从而d a1 a2 充分性 若d a1 a2 往证 1 在模m下有唯一解 证明 因为x a1 modm1 解的形式为x a1 m1y 代入 1 的二式中 得a1 m1y a2 modm2 即m1y a2 a1 modm2 于是 m1 d y a2 a1 d modm2 d 且 m1 d m2 d 1 由上节的定理5 3 1知 关于模m2 d y有唯一解y1 因此 x有解x1 a1 m1y1 若x x 都是 1 的解 则x x 0 modm1 x x 0 modm2 即m1 x x m2 x x 从而m x x 即x x mod m1 m2 定理5 4 2 秦九韶定理 证明 先不讨论普遍情形而先求li i 1 k 使适合下列特殊的合同式 li 1 modmi li 0 modmj j i 4 今j i时 mi和mj互质 故mi和互质 从而由上节定理5 3 1 有ci使 证明 取 则li适合 4 今取x a1l1 aklk 5 则模mi 故x适合 3 证明 现在证唯一性 若x x 都适合 3 则x x modmi i 1 k 故由 5 2定理5 2 4 x x modm1 mk 使用了构造性证明方法 先构造一些满足局部合同式的局部解 再把这些局部解合起来构造成整体解 证明 这里的局部合同式就是 3 中每一个同余式 即构造yi 使得yi ai modmi 而yi对其余合同式无影响 即yi 0 modmj j i 特别构造li使得 4 成立 若li已得到 则令yi aili 于是yi满足yi ai modmi yi 0 modmj j i再令x y1 yk 则x为所求 例5 4 1 求x满足同余式组 x 1 mod4 x 2 mod5 x 3 mod7 解 因为模4 5 7两两互质 所以可以用上述定理的构造性证明过程求解 先求l1 l2 l3使得 例5 4 1 l1 1 mod4 l2 1 mod5 l3 1 mod7 l1 0 mod5 l2 0 mod4 l3 0 mod4 l1 0 mod7 l2 0 mod7 l3 0 mod5 得l1 35c1 l2 28c2 l3 20c3 c1满足35c1 1 mod4 即3c1 1 mod4 从而c1 3 mod4 故l1 105 同理得l2 56 l3 120 于是x 1 105 2 56 3 120 577 17 mod140 5 4 2一元高次同余式的化简 不讲 5 4 3剩余系遍历Euler函数 在 5 中 让a1经过modm1的一个完全剩余系变化 ak经过modmk的一个完全剩余系统变化 这样 我们共得到m1 mk个x 设x a1 l1 ak lk x a1 l1 ak lk 是两个这样的x 5 4 3剩余系遍历Euler函数 5 4 3剩余系遍历Euler函数 这就是说 我们得到的m1 mk个xmodm1 mk在不同的剩余类内 但modm1 mk只有m1 mk个剩余类 所以下面的定理成立 定理5 4 4 遍历定理 设m m1 mk 而m1 mk两两互质 在 5 中 使a1 ak分别遍历modm1 modmk的各一个完全剩余系 则x遍历modm的一个完全剩余系 Euler函数 设n是任意正整数 试看modn的任意剩余类A 设a A 若a和n互质 则A中任意数和n互质 此时我们称剩余类A和n互质 事实上 若b a modn 则a b qn 倘若b和n有一个大于1的公因数d 则d也是a的因数 因而是a和n的公因数 此为矛盾 可见 若A中有一个数和n互质 则其中所有的数都和n互质 故A中的数或者都和n互质 或者都和n不互质 Euler函数 和n互质的剩余类的个数记为 n 称为Euler 欧拉 函数 从和n互质的每一个剩余类中取出一个数 这样得到的 n 个数便称之为作成modn的一个简化剩余系 显然 从modn的一个完全剩余系中取出与n互质的那些数就得到modn的一个简化剩余系 因而 n 等于 n的正数中和n互质的数的个数 例如 n 10 则modn的一个完全剩余系为0 1 9 一个简化剩余系为1 3 7 9 10 4 定理5 4 5 设m m1 mk 而m1 mk两两互质 则 m m1 m2 mk 9 这个结论实质是说在秦九韶定理证明中构造的x a1l1 aklk 若每个ai各自遍历modmi i 1 k 的一个简化剩余系 则x遍历modm的一个简化剩余系 因为ai有 mi 个取法 所以得x有 m1 mk 个取法 证明 设modmi的一个简化剩余系为Di i 1 k modm的一个简化剩余系为D 我们证明 D1 D2 Dk与D可以建立1 1映射 定义映射 如下 a1 ak x a1l1 aklk对任意 a1 ak D1 D2 Dk 有ai与mi i 1 k 互质 而x ai modmi 从而有x与mi互质 i 1 k 由定理5 2 3 x和m互质 即 是D1 D2 Dk到 内的一个映射 由遍历定理知 是单射 证明 再证 为满射 对任意x 则由遍历定理知 存在a1 ak分别属于modm modmk的完全剩余系 使得x a1l1 aklk 下面证明 a1 ak D1 D2 Dk 由于x与m互质 所以x与mi互质 而x ai modmi 因而ai与mi互质 即 a1 ak D1 D2 Dk 因此 为1 1映射 于是D的元素个数与D1 D2 Dk的元素数相同 注意到D1 D2 Dk的元素数为 m1 mk 的元素数为 m 故 m m1 mk 定理5 4 6 设是n的质因数分解式 p1 pk都不同 于是 证明 首先考虑最简单情形 n p为质数 则 n p 1 p 1 1 p 结论成立 其次考虑n pr p为质数 而求 pr 一个数a和pr互质等于说a不是p的倍数 今在从1到pr的pr个数中 是p的倍数的共pr 1个 即p 2p pr 1p因而和p互质的共pr pr 1个 故 n pr pr pr 1 pr结论成立 证明 第三考虑一般情况 p1 pk互不相同 则 pi pj 1 i j 从而 由定理5 4 5及上述第二中情形证明有 根据定理5 3 1 若 a m 1 则ax b modm 有唯一解 用另一种方法证明解的存在性 只需考虑ax 1 modm 因为若x0是ax 1 modm 的解 则可得x0b为ax b modm 的解 设r1 r m 是modm的一个简化剩余系 则 ri m 1 i 1 m 从而 r1 r m m 1 若a和n互质 则a n 1 modn 定理5 4 7 Fermat Euler定理 推论2 Fermat小定理 若p为质数 则对任意整数a都有ap a modp 费马 PierredeFermat 费马是17世纪最重要的数学家之一 从职业上来说是为律师 他是历史上最著名的业余数学家 费马的数学发现发表的很少 我们从他与其他数学家的通讯中了解他的工作 费马是解析几何的发明者之一 并且发展了微积分的某些基础思想 费马和帕斯卡尔 Pascal 为概率论建立了数学基础 费马提出了最有名的数学问题 他断定在n大于2时 方程xn yn zn没有平凡的正整数解 300多年来没有找到证明 或反例 后来的数学家称这个问题的解决是一只能够下金蛋的鸡 若想知道问题的最终结果请看下一页 谨慎的屠龙者 怀尔斯 谨慎的屠龙者 怀尔斯 谨慎的屠龙者怀尔斯因解决了350年来悬而未决的费马大定律而闻名世界 怀尔斯1953年4月11日生于英国剑桥 1971年入牛津大学学习 1980年获该校博士学位 怀尔斯的一位导师认为他具有两个显著的数学禀赋 一是他优先于一切地要去证明困难的具体定理 而不愿去作优美的无所不包的猜想 二是他有惊人的能力去吸收大量的极高深极抽象的机制 并在脚踏实地的问题中贯彻直到得出巨大的成果 费马大定理又称费马最后定理 是著名法国数学家费马在约1637年写下的一个猜想 对于任意大于2的整数n 不可能有非零的整数a b c满足 350多年很多数学家尝试过解决费马大定理 直到1993年终不能完全证明 怀尔斯在10岁读贝尔的著作 最后的难题 开始被费马达定律迷住 曾一度着手证明 但由于毫无进展而转向了椭圆曲线问题 怀尔斯 谨慎的屠龙者 1986年 肯 里贝证明 有一个尚未被证明的猜想 即所谓的谷山 志村猜想 能够导出费马大定理 可要证明这个猜想也决非易事 1986年怀尔斯得知里贝的结果后 重新燃起了研究费马大定律的热情 潜心7年 终于在1993年6月23日上午10点半左右在英国剑桥大学牛顿研究所 在连续三天的讲演的最后 概述证明了谷山 志村猜想的一大部分 从而证明了费马大定理 这一结论立刻震动了世界 有人称他为 世界的屠龙者 尽管只有极少的数学家能够理解这个技术性很强的证明 但数月后 怀尔斯的证明逐渐被发现有问题 怀尔斯继续进行非常艰苦的多种证明尝试 在一位同事的帮助下 1994年9月怀尔斯最终完成了历史性长篇论文 模椭圆曲线和费马大定理 论文于19995年发表在 数学年刊 上 怀尔斯的论文迅速得到国际数学界的承认 他因此于1996年获得沃尔夫奖 成为最年轻的沃尔夫奖获得者 习题 利用Fermat Euler定理 教材中定理5 4 7 见下例 解合同式7x 5 mod10 解 因为7和10互质 由Fermat Euler定理有7 10 1 mod10 因 10 4 所以74 1 mod10 由合同的性质7 在7x 5 mod10 两边乘以73 有73 7x 73 5 mod10 而73 7x 74x x mod10 73 5 72 7 5 1 7 5 5 mod10 所以所给合同式的解为x 5 mod10 习题 设p是一个奇质数 则 1 1p 1 2p 1 p 1 p 1 1 modp 2 1p 2p p 1 p 0 modp 3 若2m不合同于1模p 其中m是正整数 则1m 2m p 1 m 0 modp 证明 1 因为p为质数 故对于任意的1 k p 1 由Fermat小定理 知 有kp 1 1 modp 因此 1p 1 2p 1 p 1 p 1 1 1 1 p 1 1 modp 习题 2 由Fermat小定理 知 对于任意的1 k p 1 有kp k modp 故1p 2p p 1 p 1 2 p 1 p p 1 2 modp 因为p是奇数 所以 p 1 2是整数 故p p 1 2 0 modp 因此 1p 2p p 1 p p p 1 2 0 modp 习题 3 因为p为奇数 所以2与p互质 故又由1 2 p 1 是模p的简化剩余系知 2 4 6 2 p 1 也是模p的简化剩余系 它的每个数必与且只与1 2 p 1 中的一个数关于模p同余 故由合同的性质知 2m 4m 2 p 1 m 1m 2m p 1 m modp 故 2m 1 1m 2m p 1 m 0 modp 由已知 2m不合同于1模p 故2m 1不合同于0模p 又因为p为质数 由教材中合同的性质12知 1m 2m p 1 m 0 modp 习题 1 求 12371170 34 28被243除的余数 2 求7355的个位数 最后一位数 解 1 因243 35 所以由定理5 4 6知 243 243 1 162 又12371 221 mod243 2 mod243 221与243互质 于是 由Fermat Euler定理有 221162 1 mod243 即12371162 1 mod243 习题 所以 12371170 123718 123712 4 22 2 4 2 4 16 mod243 因此 123