设r为自然数,证明k可以整除phi(a^r - 1),a>=2

1个回答

  • 两个问题都是你问的?

    那我给一种不同的证明(本质其实是一样的).

    设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).