Legendre Symbol $\left(\frac4p\right)$ is always congruent to $1$?

443 Views Asked by At

Let$\newcommand\leg[2]{\left(\frac{#1}{#2}\right)}$ $\leg ap$ denote the Legendre symbol. In all cases $a=4$. and $p$ takes values of different odd prime numbers $p$.

  • For $p=5$: $\leg 45$ -> $4^{(5-1)/2} \equiv1$

  • For $p=7$: $\leg 47$ -> $4^{(7-1)/2} \equiv1$

We can keep going on and testing different primes in Legendre symbol as long as they keep being congruent to $1$.

but how can we say $\leg4p\equiv1$ for any prime $p$.

1

There are 1 best solutions below

0
On

The$\newcommand\leg[2]{\left(\frac{#1}{#2}\right)}\newcommand\ifs{\text{if }}\newcommand\qr{\text{quadratic residue}}$ Legendre-symbol $\leg ap$ is defined as $$\leg ap=\begin{cases} 1&\ifs a \text{ is a }\qr\bmod p\\ -1&\ifs a \text{ is not a }\qr\bmod p\\ 0&\ifs p\mid a. \end{cases}$$ Euler's Criterion tells us that $$\leg ap\equiv a^{(p-1)/2}\pmod p.$$

What you were doing is applying Euler's criterion. Because $4$ is a quadratic residue modulo every prime ($4$ is even a square) you're consistently getting $1$.

Note: the fact that $4$ is a square allows for an easier explanation why $4^{(p-1)/2}\equiv1\pmod p$ for every odd prime. We have $$4^{(p-1)/2}=2^{p-1}\equiv1\pmod p$$ by Fermat's little theorem.
(This is essentially how one direction of the equivalence in Euler's criterion is proved: if $a\equiv b^2$, then $a^{(p-1)/2}\equiv b^{p-1}\equiv1$.)