1.解一个方程组2x+4y=2(mod14)37x-5y=1(mod14)2.证明如果[a]在Zm中有个倒数,那么[a^n]也在Zm中有倒数.并且证明([a^n])^(-1)=[a^(-1)]^n

Question

1.
解一个方程组
2x+4y=2(mod 14)
37x-5y=1(mod 14)
2.
证明如果[a]在Zm中有个倒数,那么[a^n]也在Zm中有倒数.并且证明
([a^n])^(-1)=[a^(-1)]^n

Answer 1

1.
两个方程组上面那个是（1）下面那个是（2）
（1）*5+（2）*4：
158x=0=4x（mod14）
所以2x=0（mod7）
因为gcd（2,7）=1,所以x=0（mod7）
因为2|(2x),所以2x=0（mod14）
带入到（1）,得到4y=2（mod14）
即2y=1（mod7）
用EEA的方法：
得到2y+7s=gcd（2,7）=1的解是y=4,
所以y=4（mod 7）
所以得到答案
x=[0]in Z7
y=[4]in Z7
2.
[a][x]=1 in Zm
即ax=1(mod m)
费马小定理知道
(ax)^n=(ax)=1 (mod m)
即[a^n][x^n]=1 in Zm
所以[a^n]^(-1)=[x^n] in Zm
又费马小定理知道
[x^n]=[x]=[x]^n in Zm
所以
[a^n]^(-1)=[x^n]=[x]^n=([a]^(-1))^n
in Zm