Quadratic Reciprocity and Congruences

Question

I have to find the result of congruences : $$(a)\left(\frac{34}{73}\right)$$ $$(b)\left(\frac{36}{73}\right)$$ $$(c)\left(\frac{1356}{2467}\right)$$ By the way,I found that Theorem of Quadratic Reciprocity is for odd and prime numbers, and can somebody explain me that?

Answer 1

The second problem is trivial, $36$ is a perfect square, so is a quadratic residue modulo any prime other than $2$ or $3$.

We look at $(34/73)$ (sorry for the unconventional notation, but it is easier to type).

This is $(2/73)(17/73)$. But $(2/72)=1$ because $73$ is of the shape $8k+1$.

To compute $(17/73)$, note that since $73$ is of the shape $4k+1$, we have by Reciprocity that $(17/73)=(73/17)=(5/17)$ since $73\equiv 5\pmod{17}$.

For $(5/17)$, since at least one of $5$ or $17$ is of the form $4k+1$, we have $(5/17)=(17/5)=(2/5)$.

It is clear that $(2/5)=-1$, so $(34/73)=-1$.

For $(1356/2467)$, note that $1356=(4)(3)(113)$, so the Legendre symbol is equal to $(4/2467)(3/2467)(113/2467)$. If you have difficulty computing these, please leave a message. Note that $3$ and $2467$ are both primes of the form $4k+3$.

Remark: You asked for an explanation of quadratic reciprocity. That is a difficult thing to do, the standard first principles proofs do not provide good intuition.

But quadratic reciprocity as a computational rule is easy tp describe. If $p$ and $q$ are distinct odd primes, then $(p/q)=(q/p)$ unless both $p$ and $q$ are of the shape $4k+3$. In that case, $(p/q)=-(q/p)$.

Answer 2

In case it is the Legendre symbol you want, here is an example of such a computation for the first case. We use that the Legendre symmbol is multiplicative w.r.t. ‘numerator’; \begin{align*} \biggl(\frac{34}{73}\biggr)&=\biggl(\frac2{73}\biggr)\biggl(\frac{17}{73}\biggr)=(-1)^{\tfrac{73^2-1}8}\cdot\biggl(\frac{73}{17}\biggr)(-1)^{\tfrac{16\cdot72}4}=\frac{73}{17}=\frac{73\bmod17}{17}=\frac5{17}\\ &=\frac{17}5(-1)^{\tfrac{16\cdot4}4}=\frac25=(-1)^{\tfrac{5^2-1}8}=-1. \end{align*}

This computation requires the law of quadratic reciprocity and the 2nd supplementary law.