# Way to show that there exists $n\neq 0$ such that $n^{(p-1)/2}\neq 1 \mod p$

Suppose that $p\ge3$ is a prime and that $0\neq n \in \mathbb{Z}/p\mathbb{Z}$. Suppose also that we want to show that there is an $n$ such that $n^{(p-1)/2} \neq 1 \mod p$.

One way to show this would be to simply notice that $\mathbb{Z}/p\mathbb{Z}\setminus \{0\}$ is a cyclic group under multiplication, so that there must be an element in it which has order $p-1>(p-1)/2$.

But this exercise was put before the fact that $\mathbb{Z}/p\mathbb{Z}\setminus \{0\}$ is a cyclic group was shown, so it seems that there must be another way to show the result.

One thing I noticed by expriementing with few small values of $p$ is that $n^{(p-1)/2}=\pm 1 \mod p$ and I suspect that this is not a coincidence (so it is true for all $p$?). But I am a bit hopeless at proving that there is $n$ such that $n^{(p-1)/2}\neq 1 \mod p$.

If you have any nice idea, it'd be grateful if you could share it

• The value of $n^{(p-1)/2}\pmod p$ shows if $n$ is a quadratic residue or not. – Michael Burr Mar 1 '15 at 16:44

Since $\Bbb Z/p\Bbb Z$ is an integral domain (indeed, it is a field) the polynomial $X^{(p-1)/2}-1$ can have no more roots than its degree $(p-1)/2$. This leaves another $(p-1)/2$ nonzero$~a$ values in $\Bbb Z/p\Bbb Z$, for which $a^{(p-1)/2}\neq 1$.

The fact that those values$~a$ in fact have $a^{(p-1)/2}=-1$ is because every element$~g$ of the multiplicative group satisfies $g^{p-1}=1$ (since $p-1$ is the order of the group), so $x=a^{(p-1)/2}$ always satisfies $x^2=1$; again be a degree argument there are no more solutions for $x$ than $x=\pm1$.

• Thanks a lot! That already answers my question, but I also found out that for every value of $p$ I tested, there were exactly $(p-1)/2$ roots to the the polynomial $X^{(p-1)/2}-1$, so is there a specific reason that number of roots must be maximal? – user160738 Mar 1 '15 at 17:17
• Yes, the reason is is the answer: the polynomial $X^{p-1}-1=(X^{(p-1)/2}-1)(X^{(p-1)/2}+1)$ has exactly $p-1$ roots (all elements of the multiplicative group), and by degree considerations these must be equally distributed among the roots of its two exhibited factors. – Marc van Leeuwen Mar 1 '15 at 18:55
• Thanks a lot again, I see it now! – user160738 Mar 2 '15 at 21:27

Since $G=\mathbb{F}_p^*$ is a cyclic group isomorphic to $\mathbb{Z}/((p-1)\mathbb{Z})$, there is a generator $g$ for $G$, i.e. an element $g$ such that $o(g)=p-1$. That trivially implies:

$$g^{\frac{p-1}{2}}\not\equiv 1\pmod{p}.$$

Moreover, by the Legendre symbol we have that every non-quadratic residue $h\in G$ is such that:

$$h^{\frac{p-1}{2}}\equiv -1\pmod{p},$$ hence we just need to prove that some non-quadratic residue exists, or that the homomorphism: $$\phi : x \to x^2$$ is not surjective. That is also trivial since $\phi(x)=\phi(-x)$, giving that $\phi$ is not injective.

• OP explicitly did not want to use that the multiplicative group is cyclic. I think the Legendre symbol argument is also implicitly using that this group is cyclic. – Marc van Leeuwen Mar 1 '15 at 16:53