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?

• What exactly do you mean? Do you mean that we should explain why it is true for odd prime numbers? The proof is rather long. Commented Jan 17, 2016 at 23:29
• Nope, I need solutions for those examples, and may I use this theorem for even numbers @ChadShin Commented Jan 17, 2016 at 23:35
• There are no congruences in what you wrote. What do you mean exactly? Commented Jan 17, 2016 at 23:38
• There is. Those are quadratic congruences. I need the answer by theorem of Quadratic Reciprocity @Bernard Commented Jan 17, 2016 at 23:41
• You didn't write any congruence, you wrote fractions. Commented Jan 18, 2016 at 0:05

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

• thank you. and what is about numbers 2/73 , and 4/2467? cuz 2 and 4 are not odd and prime numbers Commented Jan 18, 2016 at 10:06
• In addition to the odd ptime stuff, we often need for computations $(2/p)=1$ if $p$ is of the form $8k\pm 1$, while $(2/p)=-1$ if $p$ is of the shape $8k\pm 3$. We also may need $(-1/p)=1$ if $p$ is of shape $4k+1$,, and $(-1/p)=-1$ if $p$ is of shape $4k+3$. The $4$ that you ask about is never a problem, since $(a^2/p)=1$ for any $a$ not divisible by $p$. Commented Jan 18, 2016 at 15:49

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.