1.证明命题 11.2。
要证 Q R p QR_pQR 
p
​
  在乘法上成群，验证 Q R p QR_pQR 
p
​
  在群公理上是否成立即可。

封闭性：

由命题 11.3 和 Q R p QR_pQR 
p
​
  的定义我们可以得知 QR*QR = QR (mod p)，那么显然乘法是封闭的。

结合律继承 Z p ∗ Z_p^*Z 
p
∗
​
  的乘法，显然。

单位元：

由 a 2 1 2 ≡ 1 2 a 2 ≡ a 2   ( m o d   p ) a^21^2 \equiv 1^2a^2 \equiv a^2 \ (mod \ p)a 
2
 1 
2
 ≡1 
2
 a 
2
 ≡a 
2
  (mod p)，有 1 2 ≡ 1   ( m o d   p ) 1^2 \equiv 1 \ (mod \ p)1 
2
 ≡1 (mod p) 为单位元。

乘法逆元存在：

对 ∀ x ∈ Q R p , ∃ a ∈ Z p ∗ \forall x \in QR_p, \exist a \in Z_p^*∀x∈QR 
p
​
 ,∃a∈Z 
p
∗
​
 ，使得 x ≡ a 2   ( m o d   p ) x \equiv a^2 \ (mod \ p)x≡a 
2
  (mod p)，那么由

x ( a − 1 ) 2 ≡ a 2 ( a − 1 ) 2 ≡ 1   ( m o d   p ) x(a^{-1})^2 \equiv a^2(a^{-1})^2 \equiv 1 \ (mod \ p)x(a 
−1
 ) 
2
 ≡a 
2
 (a 
−1
 ) 
2
 ≡1 (mod p) 可知 x − 1 ≡ ( a − 1 ) 2   ( m o d   p ) x^{-1} \equiv (a^{-1})^2 \ (mod \ p)x 
−1
 ≡(a 
−1
 ) 
2
  (mod p)。

证毕。

2.使用群论的方法证明定理 11.1。
不妨构造一个映射 ϕ : Z p ∗ → Q R p \phi:Z_p^* \rightarrow QR_pϕ:Z 
p
∗
​
 →QR 
p
​
  为 a → a 2   ( m o d   p ) , ∀ a ∈ Z p ∗ a \rightarrow a^2 \ (mod \ p), \forall a \in Z_p^*a→a 
2
  (mod p),∀a∈Z 
p
∗
​
 ，

从 Q R p QR_pQR 
p
​
  的定义我们可以得知这是一个满射，接着我们证明 ϕ \phiϕ 是一个群同态，显然，由

ϕ ( a b ) = ( a b ) 2 = a 2 b 2 = ϕ ( a ) ϕ ( b ) \phi(ab) = (ab)^2 = a^2b^2 = \phi(a)\phi(b)ϕ(ab)=(ab) 
2
 =a 
2
 b 
2
 =ϕ(a)ϕ(b) 得证。

令 K = k e r ϕ = { 1 , p − 1 } K = ker \phi = \{1,p-1\}K=kerϕ={1,p−1}，我们借此构造一个标准同态 ψ : Z p ∗ → Z p ∗ / K \psi:Z_p* \rightarrow Z_p^*/Kψ:Z 
p
​
 ∗→Z 
p
∗
​
 /K，

由第一同构定理我们可以得到 Z p ∗ / K ≅ Q P p Z_p^*/K \cong QP_pZ 
p
∗
​
 /K≅QP 
p
​
 ，那么有∣ Q R p ∣ = ∣ Z p ∗ ∣ / 2 = ( p − 1 ) / 2 |QR_p| = |Z_p^*|/2 = (p-1)/2∣QR 
p
​
 ∣=∣Z 
p
∗
​
 ∣/2=(p−1)/2，

证毕。

3.定义映射 ψ : Z p ∗ → { 1 , − 1 } 为 ψ ( a ) = ( a / p ) , ∀ a ∈ Z p ∗ \psi: Z_p^* \rightarrow \{1,-1\} 为 \psi(a) = (a/p), \forall a \in Z_p^*ψ:Z 
p
∗
​
 →{1,−1}为ψ(a)=(a/p),∀a∈Z 
p
∗
​
 。请证明这是一个满同态。
(本解题思路是基于默认 p 是一个奇素数的意识下提供的)

首先，我们可以确定这是一个满射。由定理 11.2 可得 Z_p^*恰好有 (p-1)/2 个 QR 和 (p-1)/2 个 QNR，

那么由 ψ \psiψ 的定义可得知 QR 将打在 1 上， QNR 将打在 -1 上，故 $\psi $ 必然会是一个满射。

接着确认 ψ \psiψ 是一个群同态即可。由命题 11.4可得到，

对 ∀ a , b ∈ Z p ∗ \forall a,b \in Z_p^*∀a,b∈Z 
p
∗
​
 ，ψ ( a b ) = ( a b / p ) = ( a / p ) ( b / p ) = ψ ( a ) ψ ( b ) \psi(ab) = (ab/p) = (a/p)(b/p) = \psi(a)\psi(b)ψ(ab)=(ab/p)=(a/p)(b/p)=ψ(a)ψ(b)，证毕。

4.设 p 是奇素数，证明 Z p ∗ \Z_p^*Z 
p
∗
​
  的所有生成元都是模 p 的二次非剩余。
令 g Z p ∗ Z_p^*Z 
p
∗
​
  的生成元，且 g 是一个QR，则 ∃ a ∈ Z p ∗ , g ≡ a 2   ( m o d   p ) \exist a \in Z_p^*, g\equiv a^2 \ (mod \ p)∃a∈Z 
p
∗
​
 ,g≡a 
2
  (mod p)，

那么 g 的阶应该为 p-1，即 g p − 1 ≡ a 2 ( p − 1 ) ≡ 1   ( m o d   p ) g^{p-1} \equiv a^{2(p-1)} \equiv 1 \ (mod \ p)g 
p−1
 ≡a 
2(p−1)
 ≡1 (mod p)，

这意味着 g ( p − 1 ) / 2 ≡ a p − 1 ≡ 1   ( m o d   p ) g^{(p-1)/2} \equiv a^{p-1} \equiv 1 \ (mod \ p)g 
(p−1)/2
 ≡a 
p−1
 ≡1 (mod p) 成立，也就是说 g 的阶为 (p-1)/2 < p-1，

g 显然不该是生成元，矛盾。

5.证明命题 11.4
从勒让德符号的定义上看， 1 和 3 显然是成立的。

根据命题 11.3 也可证出 2 的结论是正确的。

6.给出推论 11.1 的完整证明。
续上原证明，

p ≡ − 1   ( m o d   4 ) p \equiv -1 \ (mod \ 4)p≡−1 (mod 4)，意味着 ∃ k ∈ Z , p = 4 k + 3   ( m o d   p ) \exist k \in Z, p = 4k+3 \ (mod \ p)∃k∈Z,p=4k+3 (mod p)，

根据欧拉准则，( − 1 / p ) ≡ ( − 1 ) ( p − 1 ) / 2 ≡ ( − 1 ) ( 4 k + 3 − 1 ) / 2 ≡ ( − 1 ) 2 k + 1 ≡ − 1   ( m o d   p ) (-1/p) \equiv (-1)^{(p-1)/2} \equiv (-1)^{(4k+3-1)/2} \equiv (-1)^{2k+1} \equiv -1 \ (mod \ p)(−1/p)≡(−1) 
(p−1)/2
 ≡(−1) 
(4k+3−1)/2
 ≡(−1) 
2k+1
 ≡−1 (mod p)。

证毕。