# 3 is a primitive root modulo primes of the form 16 q^4 + 1, where q>3 is prime

**Conjecture**is a primitive root modulo for all primes , where is prime.

## Bibliography

* indicates original appearance(s) of problem.

Recomm. for undergrads: no |

Posted | by: | princeps |

on: | February 25th, 2012 |

* indicates original appearance(s) of problem.

- Subject
- Algebra (7)
- Analysis (5)
- Combinatorics (36)
- Geometry (29)
- Graph Theory (226)
- Group Theory (5)
- Logic (10)
- Number Theory (48)
- Additive N.T. (3)
- Analytic N.T. (10)
- Combinatorial N.T. (12)
- Computational N.T. (5)

- Theoretical Comp. Sci. (13)
- Topology (39)
- Unsorted (1)

- Author index
- Keyword index

## group theory answer

Using group theory, the multiplicative group of order p=16q^4+1 has order p-1=16q^4. Using lagrange's theorem, the order of any element divides the order of the group. Therefore, any element is either a primitive root, a quadratic residue, or a qth power residue mod 16q^4+1. Using the laws of quadratic reciprocity, 3 is a quadratic residue modulo a prime if and only if the prime is congruent to plus or minus 1 mod 12. Since q>3 is a prime and therefore not divisible by 3, 16q^4=1(mod 3), so 16q^4+1=2(mod 3). That means that 16q^4+1=5(mod 12), and therefore 3 is not a quadratic residue mod p. Therefore the only thing left to prove is that 3 is not a qth power residue.