Question

最大公约数

Answer 1

由(a,b)=(a-b,b)推导

设m>n

(k^m-1,k^n-1) = (k^m-k^n,k^n-1) = (k^n*(k^(m-n)-1),k^n-1)

因为(k^n,k^n-1)=1

所以 (k^n*(k^(m-n)-1),k^n-1) = (k^(m-n)-1,k^n-1)

所以(k^m-1,k^n-1) = (k^(m-n)-1,k^n-1) 根据辗转相除法的思想可知

(k^m-1,k^n-1) = k^(m,n)-1

如果你还不是很理解 可以思考一下 辗转相除法的过程.

(a,b) = (a-b,b) = ...= (c,b) = (c,b-c) = ...= (d,1)