Task 10.md

Task 10

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

证：

假设$\Z_p^*$中至少存在一个生成元$g$是模$p$的二次剩余

由欧拉准则有

$g^{(p-1)/2} = 1$

与g的阶是p-1相矛盾

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

//之前的证明

即$\Z_p^*$中存在一个群元$x$使得

$g = x^2$

由生成元的定义有

$x = g^k = x^{2k}$

$∴ e = x^{2k-1}$

显然不能由$g$生成

与$g$是生成元矛盾

$∴$假设不成立

$∴$$\Z_p^*$的所有生成元都是模$p$的二次非剩余。