0
$\begingroup$

How to compute $(\frac{234987}{9086})$? I know that Legendre symbol is $(\frac{p}{q})$ where $p \in \mathbb{Z}$ and $q$ is odd prime and Jacobi symbol is $(\frac{p}{n})$ where $p \in \mathbb{Z}$ and $n$ is odd integer. But in this case $n=9086$ is even. So is it still possible to use Jacobi symbol formula by making canonical presentation: $9086=2\cdot 5 \cdot 11 \cdot 59$ and then calculating the product of Legendre symbol of those primes? Especially I would like to know if there is need to use Quadratic reciprocity? I must make a point that although answer would be 1, it doesn't mean that $x^2 \equiv 234987 \pmod {9086}$ is solvable.

$\endgroup$
  • 1
    $\begingroup$ The Kronecker symbol generalizes the Jacobi and Legendre symbols so that you're able to take any integer "denominator." It also satisfies its own reciprocity law, and you are correct: even if $\left(\frac{a}{n}\right) = 1$, the equation $x^2\equiv a\mod n$ need not be solvable. $\endgroup$ – Stahl Jun 6 '13 at 19:35
  • $\begingroup$ In other words, you already know it is not defined, why are you trying to compute it? $\endgroup$ – Thomas Andrews Jun 6 '13 at 19:35
  • $\begingroup$ I guess I have not used Kronecker symbol before. Is it same as using Jacobi symbol? $\endgroup$ – user2723 Jun 6 '13 at 19:38
  • $\begingroup$ @Stahl: Do you mean that it cannot be solvable or "need not be solvable"? $\endgroup$ – user2723 Jun 6 '13 at 19:56
  • $\begingroup$ Need not be: if you take $\left(\frac{a}{p}\right)$ with $a$ odd and $p$ prime, the Kronecker symbol agrees with the Legendre symbol. However, if you take $\left(\frac{a}{b}\right)$ with $a,b$ satisfying the requirements for the Jacobi symbol, you can find $a,b$ such that $\left(\frac{a}{b}\right) = 1$ and $a$ a quadratic nonresidue $\mod b$. But in this case, the Kronecker symbol $\left(\frac{a}{b}\right)$ will agree with the Jacobi symbol. $\endgroup$ – Stahl Jun 6 '13 at 19:59
0
$\begingroup$

It seems that the intention of this problem is to use the Kronecker symbol. It generalizes the Jacobi and Legendre symbols so you can evaluate $\left(\frac{a}{n}\right)$ for all $n\in\Bbb Z$. If $n = u\cdot p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ is the prime factorization of $n$ with $u = \pm 1$ (a unit), then $$ \left(\frac{a}{n}\right) := \left(\frac{a}{u}\right)\prod_{i = 1}^k\left(\frac{a}{p_i}\right)^{e_i}, $$ where if $p_i$ is odd, then $\left(\frac{a}{p_i}\right)$ is the Legendre symbol, and \begin{align*} \left(\frac{a}{1}\right)&:= 1,\\ \left(\frac{a}{-1}\right)&:= \begin{cases}-1, \quad a < 0\\ 1, \quad a\geq 0\end{cases},\\ \left(\frac{a}{2}\right)&:= \begin{cases}0, \quad a\in 2\Bbb Z\\ 1, \quad a\equiv \pm 1\mod 8\\ -1,\quad a\equiv\pm 3\mod 8\end{cases},\\ \left(\frac{a}{0}\right)&:=\begin{cases}1, \quad a = \pm 1\\ 0, \quad a\neq\pm 1\end{cases}. \end{align*} It also satisfies the following reciprocity law:

Suppose $n = 2^e n'$, $m = 2^f m'$ where $n', m'\in 2\Bbb Z + 1$ (for $n = 0$, $n' = 1$), and let $n^* = (-1)^{(n' - 1)/2}n$. Then if $n\geq 0$ or $m\geq 0$, we have $$ \left(\frac{n}{m}\right) = \left(\frac{m^*}{n}\right) = (-1)^{\left(\frac{n'-1}{2}\right)\left(\frac{m'-1}{2}\right)}\left(\frac{m}{n}\right). $$ So the Kronecker symbol shares many properties (which can be found at the wikipedia page) with the Legendre and Jacobi symbols (under certain restrictions), but one needs to be a bit careful, as certain things are different.

$\endgroup$

Your Answer

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