随笔-147  评论-223  文章-30  trackbacks-0
定理:集合Z[n]由所有i=0,1,…, n-1整数组成,其中满足gcd(i,n)=1的元素与乘法模n操作形成了交换群G,且单位元为e=1。
证明:设a、b属于G,有gcd(a,n)=1,gcd(b,n)=1,则gcd(a*b,n)=gcd(b,n)=1,即(a*b) mod n封闭,显然单位元为1;根据扩展欧几里德算法得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 春秋十二月 阅读(236) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理