2
$\begingroup$

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

$\endgroup$
3
  • 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$ Apr 8, 2015 at 2:35
  • $\begingroup$ ...and also for $p=3$. $\endgroup$
    – vadim123
    Apr 8, 2015 at 2:38
  • $\begingroup$ thanks for pointing that out. I corrected the question now. $\endgroup$ Apr 8, 2015 at 2:44

1 Answer 1

3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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