b****d
发帖数: 1311 | 1 Claim: 任意正整数 $n$ 整除 $\varphi (p^n-1)$. 这里 $p$ 是个素数,
且 $\varphi(x)$ 等于不大于 $x$ 且与 $x$ 互素的正整数个数.
Recall that
$\varphi (p_1^{r_1} ... p_k^{r_k})
= p_1^{r_1-1}(p_1-1) ... p_k^{r_k-1}(p_k-1)$
where $p_1, ... ,p_k$ are distinct primes.
问: 有没有简便办法证出这个 claim 呢?
只需知道 $n=q^t$ 且 $q$ 为素数的情况.
上面 Claim 的一个证明如下:
令 $GF(p^n)$ 为包含 $p^n$ 个元素的有限域
则 $GF(p^n)=\{ 0, 1, a, a^2, ..., a^{p^n-2} \}$, 其中 $a$ 为一个
primitive $(p^n-1)$-th root of unity.
我们有 $GF(p^n)= Z_p(a)$ 且 $a$ 是 $Z_p[x]$ 中
某 $n$ 次不可约首一多项式 $f(x)$ 的零 |
|
