# Does this specific property exist for Modular Exponentiation?

$$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.
• Thanks for the answer. I'm actually trying to calculate the Legendre symbol, but I'm looking for a way to do it efficiently (which is why I'm wondering if the two congruences that I listed are related). So given the first expression that I listed, is it possible to efficiently evaluate the latter using some property of modular arithmetic? I know it will be congruent to +-1 mod p, but I'm looking to get the exact value. Jun 30, 2019 at 0:04
• @JacobG. The problem with the property: $$a^{p-1} \equiv 1 \pmod{p}$$ Is that by FLT it holds for all $a$ not divisible by $p$ so knowing that it holds tells us little about the value of the Legendre symbol (except for the fact that it is nonzero). Computing the Legendre symbol this way (i.e. by Euler criterion and using repeated squaring for exponentiation) is probably the most efficient method in terms of computational complexity. Jun 30, 2019 at 0:18