# If $a^{p-1} \equiv 1 \pmod p$ and then $a^{\frac{p-1}{2} } \equiv 1$ or $p-1 \pmod p$?

today I have some question to ask you about modular arithmetic that I'm stuck to this.

If $a^{p-1} \equiv 1 \pmod p$ then $a^{\frac{p-1}{2} } \equiv 1$ or $p-1 \pmod p$ is true or not ?

If that was true , for example $28^{29} \equiv 1$ or $58 \pmod{59}$?

I tried to find that remainder by using prime factorization of $a^{\frac{p-1}{2}}$ ,then I assume that if $2^\text{even}$ remainder is $+1$ and if $\ \ 2^\text{odd}$ remainder is $-1$ ,but certainly it failed and I think that was the most ridiculous thing I've ever done

Moreover , I will be wondering If it also can be apply to $a^{\varphi (n)} \equiv 1 \pmod n$ .

Let $b=a^{(p-1)/2}$. Note that by Fermat's Theorem we have $b^2\equiv 1 \pmod{p}$.
We show that the congruence $x^2\equiv 1\pmod{p}$ has at most two solutions. It is clear that $x=\equiv 1$ and $x\equiv p-1$ are solutions (they are the same solution if $p=2$). We show there are no others.
For if $x^2\equiv 1\pmod{p}$, then $p$ divides $(x-1)(x+1)$. But since $p$ is prime, by Euclid's Lemma we have $p$ divides $x-1$ (in which case $x\equiv 1\pmod p$) or $p$ divides $x+1$ (in which case $x\equiv -1\equiv p-1\pmod{p}$).
• I wonder if from your proof that $x^2 \equiv 1 \pmod p \implies x = \pm 1$ we can prove directly that $(\mathbb{Z}/p\mathbb{Z},\times)$ is cyclic ? Apr 2 '16 at 22:24
• I had not noticed the question at the end about $a^{\varphi(n)}$. The idea we used for prime modulus does not readily extend, since for general $n$ the congruence $x^2\equiv 1\pmod{n}$ may have many solutions. Apr 2 '16 at 22:34