定理：集合Z[n]由所有i=0,1,…, n-1整數(shù)組成，其中滿足gcd(i,n)=1的元素與乘法模n操作形成了交換群G，且單位元為e=1。
證明：設a、b屬于G，有g(shù)cd(a,n)=1，gcd(b,n)=1，則gcd(a*b,n)=gcd(b,n)=1，即(a*b) mod n封閉，顯然單位元為1；根據(jù)擴展歐幾里德算法得a*x+n*y=1，x為a的逆元，則1=gcd(a,n)=gcd(a*x,n)=gcd(x,n)，故x也在G中
posted on 2023-09-06 22:34
春秋十二月 閱讀(312)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm