1
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
12
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jacob G.
    Jun 30, 2019 at 0:04
  • 1
    $\begingroup$ @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. $\endgroup$
    – Bartek
    Jun 30, 2019 at 0:18
  • 2
    $\begingroup$ The efficient way to compute the Legendre symbol is via quadratic reciprocity. $\endgroup$ Jun 30, 2019 at 0:20
  • 1
    $\begingroup$ @Bartek Learn about the Jacobi symbol. $\endgroup$ Jun 30, 2019 at 0:33
  • 1
    $\begingroup$ @JacobG. See also this Theorem. $\endgroup$ Jun 30, 2019 at 0:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .