数论 欧拉定理证明 为何要整个完全剩余系的数相乘
来源:学生作业帮 编辑:百度作业网作业帮 分类:数学作业 时间:2024/06/16 13:23:40
数论 欧拉定理证明 为何要整个完全剩余系的数相乘
aφ(n) * x1 * x2 *...* xφ(n) mod n ≡ x1 * x2 * ...* xφ(n) mod n
aφ(n) * x1 * x2 *...* xφ(n) mod n ≡ x1 * x2 * ...* xφ(n) mod n
![数论 欧拉定理证明 为何要整个完全剩余系的数相乘](/uploads/image/z/4428862-70-2.jpg?t=%E6%95%B0%E8%AE%BA+%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86%E8%AF%81%E6%98%8E+%E4%B8%BA%E4%BD%95%E8%A6%81%E6%95%B4%E4%B8%AA%E5%AE%8C%E5%85%A8%E5%89%A9%E4%BD%99%E7%B3%BB%E7%9A%84%E6%95%B0%E7%9B%B8%E4%B9%98)
使的巧劲.
ax1*ax2*...*axxφ(n)--------------完全剩余系(自己证明两两不同余就行)
=a^φ(n) * x1 * x2 *... * xφ(n) mod n
≡ x1 * x2 * ... * xφ(n) mod n------------完全剩余系
不同的完全剩余系相乘,模n的余数是相同的.
两边出现了等量,由于(a,n)=1
所以得出a^φ(n)≡ 1 (mod n)
ax1*ax2*...*axxφ(n)--------------完全剩余系(自己证明两两不同余就行)
=a^φ(n) * x1 * x2 *... * xφ(n) mod n
≡ x1 * x2 * ... * xφ(n) mod n------------完全剩余系
不同的完全剩余系相乘,模n的余数是相同的.
两边出现了等量,由于(a,n)=1
所以得出a^φ(n)≡ 1 (mod n)