设r为自然数,证明k可以整除phi(a^r - 1),a>=2
1个回答
答过一样的题,这里贴一下.
首先有Fermat-Euler定理:
若a与m为互质的正整数,则m | a^φ(m)-1.
再补充一个引理:
若a与m是正整数,d是使m | a^d-1的最小正整数.
如果正整数k也满足m | a^k-1,则有d | k.
证明:由带余除法,可设k = qd+r,其中q,r为正整数,0 ≤ r < d.
由m | a^d-1,有m | (a^d-1)(a^((q-1)d)+...+a^d+1) = a^(qd)-1.
进而m | a^r·(a^(qd)-1) = a^(qd+r)-a^r = a^k-a^r.
又m | a^k-1,故m | (a^k-1)-(a^k-a^r) = a^r-1.
由0 ≤ r < d,而d是使m | a^d-1的最小正整数,只有r = 0.
从而k = qd,即d | k.
用上面两个结论能立即完成证明.
对正整数r,取m = a^r-1.
显然,使m | a^d-1的最小正整数d = r.
又易知a与m互质,由Fermat-Euler定理,m | a^φ(m)-1.
再由引理即得r | φ(m) = φ(a^r-1).
相关问题
