0
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ thank you. and what is about numbers 2/73 , and 4/2467? cuz 2 and 4 are not odd and prime numbers $\endgroup$ – Function Jan 18 '16 at 10:06
  • 1
    $\begingroup$ 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$. $\endgroup$ – André Nicolas Jan 18 '16 at 15:49
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.