Quadratic reciprocity

Note that \(p = 3\) works. It remains to consider the case that \(p > 3\), which we assume from now on.

Claim. Let \(p > 3\) be a prime number. Assume that \(4p + 1\) divides \(3^p - 1\). Then \(4p + 1\) is a prime number.

Proof of the claim. On the contrary, assume that \(4p + 1\) is composite, and hence it has an odd prime divisor \(q\) such that \(q \leq \sqrt{4p + 1}\). Note that the order of \(3\) modulo \(q\) divides both \(p\) and \(q - 1\). Since \(q\) is odd, it follows that the order of \(3\) modulo \(q\) is equal to \(p\). Therefore, \(p\) divides \(q - 1\), which yields \[ 4p + 1 \geq q^2 \geq (p + 1)^2, \] which is false for \(p \geq 3\). This proves the claim.

Let \(p > 3\) be a prime number such that \(4p + 1\) divides \(3^p - 1\). Since \(4p + 1\) is a prime and it divides \(3^p - 1\), it follows that \(3\) is a quadratic residue modulo \(4p + 1\). Also note that \(3\) is a nonzero quadratic residue modulo \(4p + 1\). By the quadratic reciprocity law, we have that \(4p + 1\) is a quadratic residue modulo \(3\). This implies that \(4p + 1 \equiv 1 \pmod{3}\), which is equivalent to \(p \equiv 0 \pmod{3}\). This contradicts that \(p > 3\) is a prime. Therefore, \(p = 3\) is the only prime number such that \(4p + 1\) divides \(3^p - 1\).