CINTA_09

发表于 2022-12-18 分类于 CINTA 阅读次数：

六、设\(p\)是奇素数，请证明\(Z_p^*\)的所有生成元都是模\(p\)的二次非剩余。

解：

由题得，任取\(g\)为\(Z_p^*\)的生成元，因为\(Z_p^*\)的阶为\(p-1\),所以\(g\)的阶为\(p-1\)，即有\(g^{p-1}\equiv\ 1\ (mod\ p)\)

假设\(g\)是模\(p\)的二次剩余，即存在\(a\in Z_p^*,g\equiv x^2(mod\ p)\)成立

所以有\(g^{(p-1)}\equiv a^{2(p-1)}\equiv 1\ (mod\ p)\)，由费马小定理得\(a^{(p-1)}\equiv 1\ (mod\ p)\).

所以\(g^{(p-1)/2}\equiv a^{(p-1)}\equiv 1\ (mod\ p)\),

与\(g\)的阶为\(p-1\)矛盾，

所以\(Z_p^*\)的所有生成元都是模\(p\)的二次非剩余.

七、使用抽象代数的语言重新证明欧拉准则。

证明：对任意正整数\(n\)，根据二次剩余定理，\(n\)不是模\(p\)的二次剩余就是模\(p\)的非二次剩余，

因为\(p\)是奇素数，由费马小定理得\(n^{p-1}\equiv 1\ (mod\ p)\),即\(n^{(p-1)/2}\equiv \pm1\ (mod\ p)\).

所以即证\(n\)是模\(p\)的二次剩余当且仅当\(n^{(p-1)/2}\equiv1\ (mod\ p)\)

充分性：已知条件为存在\(a\in Z,n\equiv a^2\ (mod\ p)\),

加上费马小定理，所以有\(n^{(p-1)/2}\equiv a^{p-1}\equiv1\ (mod\ p)\)，得证.

必要性：设\(g\)是模\(p\)的一个原根，那么一定存在一个正整数k使得 \(g^k\equiv n(mod\ p)\);

又因为 \(n^{(p−1)/2}\equiv1(mod\ p)\); 所以\((g^k)^{(p-1)/2}\equiv1\ (mod\ p)\);

因为\(g\)是原根，所以一定存在\((p-1)|k*\frac{p-1}{2}\),

所以\(k\)为偶数，即存在\(x\),\(x\equiv g^{k/2}\ (mod\ p)\);

有\(x^2\equiv n\ (mod\ p)\),

所以\(n\)是模\(p\)的二次剩余。

所以欧拉准则得证.