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. – Chad Shin Jan 17 '16 at 23:29
• Nope, I need solutions for those examples, and may I use this theorem for even numbers @ChadShin – Function Jan 17 '16 at 23:35
• There are no congruences in what you wrote. What do you mean exactly? – Bernard Jan 17 '16 at 23:38
• There is. Those are quadratic congruences. I need the answer by theorem of Quadratic Reciprocity @Bernard – Function Jan 17 '16 at 23:41
• You didn't write any congruence, you wrote fractions. – Bernard Jan 18 '16 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 – Function Jan 18 '16 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$. – André Nicolas Jan 18 '16 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.