Question

Prove Euler’s criterion, which states that if p is an odd prime and a is a positive integer not divisible by p, then$\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}(modp)$

Short answer

$\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}(modp)$

Step-by-step solution

Step: 1

We will first let a is a quadratic residue.

$\frac{a}{p}=1$

Then $\text{and}a=x^2$

for some integer x.

By applying Fermat’s Little Theorem now

role="math" localid="1668595209756" $\begin{array}{r}{a}^{(p-1)/2}=(x{)}^{(p-1)/2}\\ x^{p-1}=1(modp)\end{array}$

Step: 2

Now, if a is not a quadratic residue we will consider a set$\{1,2,3,\dots ,p-1\}$

If this set is grouped as a product, we get

$\begin{array}{r}(p-1)!=a^{\frac{p-1}{2}}\\ (p-1)!=a^{\frac{p-1}{2}}modp\\ (p-1)!=-1modp\end{array}$