---
# System prepended metadata

title: p=4q+1

---

# p=4q+1
## 題目
$p, q$是質數滿足$p=4q+1$，證明2是$p$的原根
## 證明
$\because 2$是二次剩餘$\iff p\equiv\pm1\mod 8$，$p\equiv 4q+1\equiv 5\mod 8$
$\therefore 2$在模$p$下不是二次剩餘，即$2^{\frac{p-1}2}\equiv 2^{2q}\equiv-1\mod p$
$\Rightarrow\lambda_p(2)|4q$ but $\lambda_p(2)\nmid 2q$
$\Rightarrow\lambda_p(2)=4$或$4q$
若$\lambda_p(2)=4\Rightarrow 2^4\equiv 1\mod p\Rightarrow p=3, 5$ but $q\geq 2$
所以$\lambda_p(2)=4q=p-1\Rightarrow 2$是$p$的原根