# Legendre symbol, a theoretical question.

I need to show that if $p$ is a prime number of the form $p=4m+1$, then for any divisor $d$ of $m$: $$\left(\frac{d}{p} \right) = 1$$ where $\left(\frac{d}{p} \right)$ is the Legendre symbol.

My thought was to assume first that $d$ is a prime number, then since $p \not\equiv 3 \mod4$, we get: $$\left(\frac{d}{p} \right) = \left(\frac{p}{d} \right)= \left(\frac{4qd+1}{d} \right)= \left(\frac{1}{d} \right)=1$$ And since it's true for any prime divisor of $m$, by the multiplicity of Legendre symbol, it's true for any product of primes that divides $m$, thus true for any divisor.

Is this ok?

• To use multiplicatiity, you will need to deal with $d$ that are prime powers. But that is no problem. If $d=q^a$ where $a$ is even, then $(d/p)=1$. And if $a$ is odd, then $(d/p)=(q/p)$, and you can argue as in the OP. – André Nicolas May 24 '15 at 17:34

If $4m+1$ is prime, you want to show $\,d\mid m\,\Rightarrow\, \left(\frac{d}{4m+1}\right)=1$

Let $d=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\mid m$. QR - quadratic reciprocity.

$p_i$ is odd $\,\Rightarrow\,$ $\left(\frac{p_i}{4m+1}\right)\stackrel{\text{QR}}=\left(\frac{4m+1}{p_i}\right)=\left(\frac{1}{p_i}\right)=1$

$p_i=2\,\Rightarrow\, m=2n\,\Rightarrow\,\left(\frac{p_i}{4m+1}\right)=\left(\frac{2}{8n+1}\right)\stackrel{\text{QR}}=1$

$\left(\frac{d}{4m+1}\right)=\left(\frac{p_1}{4m+1}\right)^{\alpha_1}\left(\frac{p_2}{4m+1}\right)^{\alpha_2}\cdots\left(\frac{p_k}{4m+1}\right)^{\alpha_k}=1\cdot 1\cdots 1=1$

or simply observe that $p_i\equiv x_i^2\pmod{\! 4m+1}$ for some $x_i$ implies

$d\equiv \left(x_1^2\right)^{\alpha_1}\left(x_2^2\right)^{\alpha_2}\cdots \left(x_k^2\right)^{\alpha_k}\equiv \left(x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_k^{\alpha_k}\right)^2\pmod{\! 4m+1}$

That's a good start.

You have deal with the case $d=2$ separately - your argument only works for $d$ an odd prime.

Other than that, your proof works. You don't need full multiplicity of Legemdre, just that any product of perfect squares is a perfect square.