数论 欧拉定理证明 为何要整个完全剩余系的数相乘aφ(n) * x1 * x2 *...* xφ(n) mod n ≡ x1 * x2 * ...* xφ(n) mod n

来源:学生作业帮助网 编辑:作业帮 时间:2024/11/06 09:51:44

数论 欧拉定理证明 为何要整个完全剩余系的数相乘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

数论 欧拉定理证明 为何要整个完全剩余系的数相乘aφ(n) * x1 * x2 *...* xφ(n) mod n ≡ x1 * x2 * ...* xφ(n) 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)