ช่วยพิสูจน์ Number หน่อยคร้าา

[pormath]

ให้ pและ q เป็นจำนวนเฉพาะคี่ ซึ่ง p\equiv 1(mod4) และq = 2p +1 จงพิสูจน์ว่า 2 เป็น primitive root modulo q

[Anton]

Problem. Let $p$ and $q$ be odd prime natural numbers. If $p\equiv 1\pmod{4}$ and $q=2p+1$, then verify that $2$ is a primitive element modulo $q$.

Let $k$ be the smallest possible positive integer such that $2^k\equiv 1\pmod{q}$. By Fermat's Little Theorem, we also know that $2^{q-1}\equiv 1\pmod{q}$. That is,
$$2^{\gcd(k,q-1)}\equiv 1\pmod{q}\,.$$
By minimality of $k$, we must have $\gcd(k,q-1)=k$. Therefore, $k\mid q-1=(2p+1)-1=2p$. This means $k\in\{1,2,p,2p\}$.

If $k=1$, then from $2^k\equiv 1\pmod{q}$, we get $2\equiv 1\pmod{q}$, whence $q\mid 2-1=1$, which is absurd. If $k=2$, then $2^k\equiv 1\pmod{q}$ implies that $2^2\equiv 1\pmod{q}$, so $q\mid 2^2-1=3$. Thus, $q=3$, but then from $q=2p+1$, we get $p=1$, which is again a contradiction. If $k=p$, then $2^p=2^k\equiv 1\pmod{q}$, so that
$$\left(2^{\frac{p+1}{2}}\right)^2=2^{p+1}=2\cdot 2^p\equiv 2\cdot 1=2\pmod{q}\,.$$
Thus, $2$ is a quadratic residue modulo $q$. However, $q=2p+1$ and $p\equiv 1\pmod{4}$ imply that $q\equiv 3\pmod{8}$. However, $\left(\dfrac{2}{q}\right)=(-1)^{\frac{q^2-1}{8}}=-1$ implies that $2$ is not a quadratic residue modulo $q$. This is another contradiction. Hence, $k=2p=q-1$. Therefore, $2$ is a primitive element modulo $q$.