二次剩余 练习题

hbghlyj

Number Theory 2019 sheet 2
Lecture notes pdf

• 假设 $p$ 和 $q=2p+1$ 都是奇素数。为什么：
  (a) $2p$ 是 $q$ 的二次非剩余；
  (b) $q$ 有 $p-1$ 个本原根。
  证明 $q$ 的本原根恰好是 $q$ 的二次非剩余，除了 $2p$。
• 将第2题发到了这帖
• 设 $p$ 是一个奇素数。证明 $\mathbb{Z} / p \mathbb{Z}$ 中的每个元素都可以表示为两个平方数之和。
• 是否存在整数解使得方程 $x^{2} \equiv 251 \bmod 779$ 成立？注意 $779=19 \times 41$。
• 方程 $x^{2}+10x+15 \equiv 0 \bmod 45083$ 是否有整数解？注意 45083 是素数。
• 使用费马方法分解 9579，不要使用计算器。
• 将第7题发到了这帖
• 利用费马方法，分解 2881，从而计算出 $\phi(2881)$。

  ---

  一条消息已使用 RSA 加密，编码为 $01 \leftrightarrow A,02 \leftrightarrow B, 03 \leftrightarrow C$ 等，指数 $e=5$，模数 $n=2881$。
  加密的信息是 2352 2138 0828。明文信息是什么？
• 设 $p\ge7$ 是一个奇素数。证明 $\mathbb{Z} / p \mathbb{Z}$ 中的每个非零元素都可以表示为两个非零平方数之和。

hbghlyj

6. 仿照Example 5.1.计算如下
$97<\sqrt{9579}<98$ 所以我们开始檢視 $m = 98$，发现：
$98^2-9579=25=5^2$
因此 $9579=98^2-5^2=93\times103$

8. 仿照Example 5.1.计算如下
$53<\sqrt{2881}<54$ 所以我们开始檢視 $m = 54$, 发现：
$54^2-2881=35$
$55^2-2881=144=12^2$
因此 $2881=43\times67$，因为 43 和 67 为质数，$\phi(2881)=42·66=2772$

---

幂模PowerMod[{2352, 2138, 828}, PowerMod[5, -1, 2772], 2881]结果是{1524, 615, 1804}
取出对应的字母Alphabet[][[#]] & /@ {15, 24, 6, 15, 18, 4}结果是oxford

hbghlyj

3. 对于所有奇素数 $p$，对于所有 $k$，存在 $x, y$ 使得 $x^2 + y^2\equiv k \pmod{p}$。
证明：模 $p$ 有 $(p+1)/2$ 个平方数，所以有 $(p+1)/2$ 个数 $x^2$，以及 $(p+1)/2$ 个数 $k-y^2$，因此这两个集合必须重叠，在它们重叠的地方得到 $x^2=k-y^2\pmod p$。

---

9. MSE
由第3题，$\mathbb{Z} / p \mathbb{Z}$ 中的每个元素都可以表示为两个平方数之和，但这里要求非零，所以如果遇到非零的$a$被第3题写成$a=0^2+b^2$，则需要重新写成两个非零平方数之和：
$$a=b^2=(3b/5)^2+(4b/5)^2$$

hbghlyj

第1题