一道数论题

习题6.2 9

Problem：若 \(p\) 是形如 \(2^n +1 (n \geq 2)\) 的素数，则 \(3\) 是模 \(p\) 的原根。

Proof: 由费马小定理

\[3^{2^n} \equiv 1 \pmod{2^n+1}\]

于是只要证明 \(3^{2^{n-1}} \not\equiv 1 \pmod{2^n+1}\) 即可。

注意到，由欧拉定理 \((\dfrac{3}{2^n+1}) \equiv 3^{\frac{2^n}{2}}\equiv 3^{2^{n-1}} \pmod{2^n+1}\)

而 \(3\) 是 \(p\) 的二次剩余当且仅当 \(p \equiv \pm 1 \pmod {12}\)

于是 \(3\) 不是 \(p\) 的二次剩余，命题得证。

难得做到这么简单的数论题呜呜呜