信息安全数学基础的习题：设m,n为正整数,a>1是整数证明:(a^m-1,a^n-1)=a^(m,n)-1a^m表示的意思是a的m次方,以此类推后面的是a的(m,n)的次方,（m,n）表示m与n的最大公因数

Question

信息安全数学基础的习题：设m,n为正整数,a>1是整数 证明:(a^m-1,a^n-1)=a^(m,n)-1
a^m表示的意思是a的m次方,以此类推后面的是a的(m,n)的次方,（m,n）表示m与n的最大公因数

Answer 1

设 (m,n)=d, m=dm1, n=dn1,
需要公式 x^k-y^k=(x-y)[x^(k-1)+x^(k-2)*y+x^(k-3)*y^2+.+y^(k-1)]
a^m-1=a^(m1d)-1=(a^d)^m1-1
=(a^d-1){a^[(m1-1)d]+a^[(m1-2)d]+a^[(m1-3)d]+...+1}
a^m-1=(a^d-1){a^[(m=n1-1)d]+a^[(n1-2)d]+a^[(n1-3)d]+...+1}
余下来就是证明
a^[(m1-1)d]+a^[(m1-2)d]+a^[(m1-3)d]+...+1与a^[(m=n1-1)d]+a^[(n1-2)d]+a^[(n1-3)d]+...+1
互素,可以用欧几里得算法得到证明.