0
$\begingroup$

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

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

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user160738 Mar 1 '15 at 17:17
  • 1
    $\begingroup$ 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. $\endgroup$ – Marc van Leeuwen Mar 1 '15 at 18:55
  • $\begingroup$ Thanks a lot again, I see it now! $\endgroup$ – user160738 Mar 2 '15 at 21:27
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Marc van Leeuwen Mar 1 '15 at 16:53

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.