$$a^{p-1} \equiv 1 \pmod p$$
Assuming the above expression is true, does it tell me anything about the congruence relation of the following expression:
$$a^{\frac{p-1}{2}} \pmod p)$$
I can't seem to come to a conclusion by using properties of modular exponentiation that I find online. My goal is to somehow relate the two so I can efficiently evaluate the second expression when using very large values.
Note: $a$ is some positive integer less than $p$, and $p$ is a prime number.
Yes it can (we are assuming that $p \not \mid a$). We know that: $$(a^{\frac{p-1}{2}})^2 \equiv a^{p-1} \equiv 1 \pmod{p}$$ And since for any number $x$ such that $x^2 \equiv 1 \pmod{p}$ we have $p \mid x^2-1=(x-1)(x+1)$ and therefore $p \mid x-1$ or $p \mid x+1$ and therefore $x \equiv \pm 1 \pmod{p}$ we can conclude that: $$a^{\frac{p-1}{2}} \equiv \pm 1 \pmod{p}$$ Actually, by Euler's criterion we have even stronger result: $$a^{\frac{p-1}{2}} \equiv \left( \frac{a}{p}\right) \pmod{p}$$ Where $\left( \frac{a}{p}\right)$ denotes the Legendre symbol, i.e. it is $0$ when $p \mid a$, $1$ when $a$ is quadratic residue modulo $p$ and $-1$ when it isn't.