4
$\begingroup$

for $N \ge 4$. Show for prime numbers, $p \equiv 1$ mod $(N!)$ that none of the numbers $1,2,...,N$ are primitive roots modulo $p$

I can't figure out where to start with this question, all I can think to use is the Legendre symbol and Euler's Criterion but I haven't been able to do it. Any help would be much appreciated.

$\endgroup$
3
$\begingroup$

The prime $p$ is of the form $8k+1$, so $2$ is a quadratic residue of $p$.

Next we show that every odd prime $\le N$ is also a quadratic residue of $p$. From this it will follow that any integer $w$ whose prime divisors are $2$ and/or primes $\le N$ is a quadratic residue of $p$, and therefore not a primitive root of $p$.

A Legendre symbol calculation does it. Let $q$ be an odd prime $\le N$. By Quadratic Reciprocity, the Legendre symbol $(q/p)$ is equal to $(p/q)$. But $p\equiv 1\pmod{q}$, and therefore $(p/q)=(1/q)=1$.

$\endgroup$
  • $\begingroup$ You are welcome. $\endgroup$ – André Nicolas Feb 11 '15 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.