作业帮设r为自然数,证明k可以整除phi(a^r - 1),a>=2
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/09 06:08:40
设r为自然数,证明k可以整除phi(a^r - 1),a>=2
设r为自然数,证明k可以整除phi(a^r - 1),a>=2
设r为自然数,证明k可以整除phi(a^r - 1),a>=2
两个问题都是你问的?
那我给一种不同的证明(本质其实是一样的).
设m = a^r-1,n = φ(m).
由定义,φ(m)就是1至m中与m互质的整数的个数.
更方便的说法是mod m的既约剩余系类的个数(若对这个概念不熟悉,
若能将mod m的既约剩余类分组,使每组恰有r个,那么就证明了结果.
若b与m互质,考虑r个数:b,b·a,b·a^2,b·a^3,...,b·a^(r-1).
可知它们都与m互质(因为a,b都与m互质),从而它们除以m的余数也与m互质.
此外它们除以m的余数互不相同:
若不然,假设对r > i > j ≥ 0成立m | b·a^i-b·a^j = b·a^j·(a^(i-j)-1).
由m与b和a互质,有m | a^(i-j)-1,但0 < a^(i-j)-1 < a^r-1 = m,矛盾.
于是我们将一个mod m的既约剩余类与另外r-1个既约剩余类分成了一组.
对于组内的任意一个元素,例如c = b·a^k.
按分组方法,它应与c,c·a,c·a^2,c·a^3,...,c·a^(r-1)所在的既约剩余类分为一组.
用b写出来是b·a^k,b·a^(k+1),b·a^(k+2),...,b·a^(k+r-1).
而由a^r = 1 (mod m),有b·a^r = b (mod m),b·a^(r+1) = b·a (mod m),...
因此由c产生的分组和b是一样的,即分组结果与选取的是组内哪个元素无关.
于是两个不同分组一定没有公共元素,否则两组都可由公共元素按分组方法产生,两组完全相同.
由于每个mod m的既约剩余类恰好包含在一组中,而每组恰有r个元素,
即得mod m的既约剩余类个数被r整除,也即r | φ(m) = φ(a^r-1).