Does Fermat's Little Theorem tell us anything about $a^{\frac{p - 1}{2}}$?

55 Views Asked by At

Fermat's Little Theorem states that, if $p$ does not divide $a$, then:

$$a^{p - 1} \equiv 1 \pmod{p}$$

From this, can we derive the following:

$$a^{\frac{p - 1}{2}} \equiv \, ?\pmod{p}$$

If not, is there an answer to what $?$ should be in the above congruence?

2

There are 2 best solutions below

0
On

Since $(a^{\frac{p-1}2})^2\equiv a^{p-1}\equiv 1\pmod p,$ $(a^{\frac{p-1}2})^2-1\equiv (a^{\frac{p-1}2}-1)(a^{\frac{p-1}2}+1)\equiv 0\pmod p,$ so $a^{\frac{p-1}2}\equiv \pm 1\pmod p.$

0
On

Fermat is equivalent to $a^{\frac{p-1}{2}}\equiv \pm 1 \pmod p$. This is because the congruence $x^2 \equiv 1 \pmod p$ has exactly two solutions $\pm 1$.