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

  • 3
    $\begingroup$ $\left({4\over p}\right)=\left({2\over p}\right)^2$ i.e. $4$ is always a square, because $4=2^2$. $\endgroup$ – Adam Hughes Apr 8 '15 at 2:35
  • $\begingroup$ ...and also for $p=3$. $\endgroup$ – vadim123 Apr 8 '15 at 2:38
  • $\begingroup$ thanks for pointing that out. I corrected the question now. $\endgroup$ – 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$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.