MingLLuo

CINTA-HW8

  • Dec 12, 2022
  1. 使用群论的第一同构定理证明定理11.1。
    • 令$\psi: g\rightarrow g^2$，$\mathbb{Z}_p^ \ast \mapsto\mathbb{H}$，$\psi$是一种群同态映射，且$Ker\ \psi=\lbrace 1, p-1\rbrace$
    • 由第一同构定理知$\vert \mathbb{H}\vert=\vert\mathbb{Z}_p^ \ast /\mathbb{K}\vert = (p-1)/2$，即存在$(p-1)/2$个QR，余下$(p-1)/2$个QNR
  2. 证明命题11.2
    • 将$QR_p$表示为${x_0^2, x_1^2,….,x_m^2},x_i\in\mathbb{Z}_p$
    • 满足结合律
    • 存在单位元e=1
    • 存在逆元，因为$e = x_i^2 \ast x_i^{-1} \ast x_i^{-1}=x_i^2 \ast (x_i^{-1})^2$
  3. 定义映射$\psi:\mathbb{Z}_p^ \ast \rightarrow{\pm1}$为$\psi(a)=\left(\frac{a}{p}\right)$，$\forall a\in\mathbb Z_p^ \ast ,p>2$。请证明这是一种满同态。提示：${\pm1}$在乘法上成群。
    • $\psi(ab)=\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \left(\frac{b}{p}\right)=\psi(a)\psi(b)$，故满足同态
    • 当$p>2$时，其存在QR与QNR，等价于$\psi$必然产生$\pm 1$，故满射，即该映射为满同态映射
  4. 证明命题11.4。
    • 由性质得，等式1成立
    • $\left(\frac{ab}{p}\right) = (ab)^{(p-1)/2}=a^{(p-1)/2}b^{(p-1)/2}=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$，得证
    • $x^2\equiv a^2\pmod p$有解，$x\equiv a\pmod p$，故$\left(\frac{a}{p}\right)=1$
  5. 给出推论11.1的完整证明
    • 当$p\equiv 1\pmod 4, p = 4k +1$，$\left(\frac{-1}{p}\right) \equiv (-1)^{(p-1)/2}\equiv(-1)^{2k}\equiv 1\pmod p$
    • 当$p\equiv -1\pmod 4, p = 4k +3$，$\left(\frac{-1}{p}\right) \equiv (-1)^{(p-1)/2}\equiv (-1)^{2k+1}\equiv -1\pmod p$
  6. 设$p$是奇素数，请证明$\mathbb Z_p^ \ast $的所有生成元都是模$p$的二次非剩余。应用欧拉准则立得
    • 令生成元为$g$，其阶为p，则$g^{(p-1)/2}\not \equiv 1 \pmod p$
    • 故所有生成元都是模$p$的二次非剩余
  7. 使用抽象代数的语言重新证明欧拉准则。
    • 对于模奇素数意义下的群$\mathbb{Z}_p$，任意非单位元元素$x$都是生成元
    • 则$x^{p-1}\equiv (x^2)^{\frac{p-1}{2}}\equiv 1 \pmod p$，由定义知若$\left(\frac{a}{p}\right)=1$，则有$x^2 \equiv a\pmod p$，$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\equiv 1\pmod p$
    • 若$\left(\frac{a}{p}\right)=-1$，易知$a^{\frac{p-1}{2}}\equiv -1\pmod p$，此时$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\equiv -1\pmod p$
  8. 利用二次互反律，写程序完成$\left(\frac{q}{p}\right)$的计算，$p$和$q$是任意的奇素数。 
    # p%4 == 3 and q %4 == 3?
 # reverse  \ast  -1
# if p or q %4 == 1
 # reverse
# small enough
 # sage legendre_symbol
  9. 设$n=7 \ast 11$，$a=4$，请手动计算求$x$使得$x^2\equiv a\pmod{n}$
    • 先求解$x_1^2\equiv 4 \pmod{7}$和$x_2^2\equiv 4\pmod{11}$
  10. 对大于$2$的素数$p$计算$2^{(p-1)/2}\bmod{p}$，根据计算结果找规律，并形成自己的猜想，最后给出证明。
    • 猜想：当$p\equiv 1 或 7 \pmod 8$时，结果为1，当$p\equiv 3 或5\pmod 8$时，结果为$p-1$
    • 证明：我们知道$2^{\frac {p-1} {2}}(\frac {p-1} {2})! \equiv 2 \ast ….\ast(p-1)\equiv (-1)^x (\frac {p-1} {2})!\pmod p$，$x$为大于$\frac {p-1} {2}$的元素个数
    • 当$p=1+8k,(p-1)/2=4k,x=(8k-(4k+2))/2+1=2k$，故为1
    • 当$p=7+8k,(p-1)/2=4k+3,x=(8k+6-(4k+4))/2+1=2k+2$，故为1
    • 当$p=3+8k,(p-1)/2=4k+1,x=(8k+2-(4k+2))/2+1=2k+1$，故为-1
    • 当$p=5+8k,(p-1)/2=4k+2,x=(8k+4-(4k+4))/2+1=2k+1$，故为-1
© MingLLuo
Search