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?
$\begingroup$
$\endgroup$
12
-
$\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 ShinCommented Jan 17, 2016 at 23:29
-
$\begingroup$ Nope, I need solutions for those examples, and may I use this theorem for even numbers @ChadShin $\endgroup$– FunctionCommented Jan 17, 2016 at 23:35
-
$\begingroup$ There are no congruences in what you wrote. What do you mean exactly? $\endgroup$– BernardCommented Jan 17, 2016 at 23:38
-
$\begingroup$ There is. Those are quadratic congruences. I need the answer by theorem of Quadratic Reciprocity @Bernard $\endgroup$– FunctionCommented Jan 17, 2016 at 23:41
-
1$\begingroup$ You didn't write any congruence, you wrote fractions. $\endgroup$– BernardCommented Jan 18, 2016 at 0:05
|
Show 7 more comments
2 Answers
$\begingroup$
$\endgroup$
2
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)$.
answered Jan 18, 2016 at 0:12
-
$\begingroup$ thank you. and what is about numbers 2/73 , and 4/2467? cuz 2 and 4 are not odd and prime numbers $\endgroup$– FunctionCommented Jan 18, 2016 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$ Commented Jan 18, 2016 at 15:49
$\begingroup$
$\endgroup$
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.
