第八次作业

第八次作业

1.设是的生成元，因为是奇素数，那么的阶是。

假设是模的二次剩余，则有：存在。

可得。由费尔马小定理可得。

与假设矛盾。所以不是模的二次剩余。

2.由二次剩余的定义可得：对于奇素数，如果存在一个正整数，且，那么要么是的二次剩余，要么就是二次非剩余。

由费尔马小定理可得，因为，且，那么我们只需要证明：是的二次剩余当且仅当。

充分性：

是的二次剩余，那么有。所以。充分性得证。

必要性：

，假设是的一个原根，那么我们可以得到：存在一个正整数使得，所以

。

因为是原根，我们知道，所以一定存在，所以是偶数，使得，

那么有。所以是模的二次剩余。

综上所述，欧拉准则得证。