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

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

• $\left({4\over p}\right)=\left({2\over p}\right)^2$ i.e. $4$ is always a square, because $4=2^2$. – Adam Hughes Apr 8 '15 at 2:35
• ...and also for $p=3$. – vadim123 Apr 8 '15 at 2:38
• thanks for pointing that out. I corrected the question now. – Mansi Jolly Apr 8 '15 at 2:44

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