3
$\begingroup$

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

Thank you for every comments in advance.

$\endgroup$
1
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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 ? $\endgroup$
    – reuns
    Apr 2 '16 at 22:24
  • $\begingroup$ I am pretty sure that we cannot. One of the usual proofs uses facts about polynomial congruences, but quadratic congruences are not enough. $\endgroup$ Apr 2 '16 at 22:31
  • $\begingroup$ 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. $\endgroup$ Apr 2 '16 at 22:34

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.