ช่วยพิสูจน์ Number หน่อยคร้าา
ให้ pและ q เป็นจำนวนเฉพาะคี่ ซึ่ง p\equiv 1(mod4) และq = 2p +1 จงพิสูจน์ว่า 2 เป็น primitive root modulo q
|
อ้างอิง:
$$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$. |
เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 13:26 |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha