3
$\begingroup$

The definition and properties of Jacobi symbol are stated in this article. I don't have a textbook handy containing the proofs of the following properties of Jacobi symbol. It seems to me that not many textbooks on elementary number theory contain them. So I think it is nice not only for me but also for other users to have them here assuming the corresponding properties of Legendre symbol.

1. Let $n$ be a positive odd integer. Let $a, b$ be integers such that $a \equiv b$ (mod $n$). Then $$\left(\frac{a}{n}\right) = \left(\frac{b}{n}\right)$$

2. Let $a$ be an integer. Let $m, n$ be positive odd integers. Then $$\left(\frac{a}{mn}\right) = \left(\frac{a}{m}\right)\left(\frac{a}{n}\right)$$

3. Let $a, b$ be integers. Let $n$ be a positive odd integer. Then $$\left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$$

4. Let $m, n$ be positive odd integers such that gcd$(m,n) = 1$. Then $$\left(\frac{m}{n}\right) \left(\frac{n}{m}\right) = (-1)^{\frac{m-1}{2}\frac{n-1}{2}}$$.

5. Let $n$ be a positive odd integer. Then $$\left(\frac{-1}{n}\right) = (-1)^{\frac{n-1}{2}}$$.

6. Let $n$ be a positive odd integer. Then $$\left(\frac{2}{n}\right) = (-1)^{\frac{n^2-1}{8}}$$.

$\endgroup$
  • 2
    $\begingroup$ As they are all well known, why not just search them up? Regardless, most of these follow almost immediately from the corresponding properties for Legendre Symbols. $\endgroup$ – tc1729 Oct 25 '13 at 6:22
  • 1
    $\begingroup$ As @tc1729 notes, these are mostly immediate consequences of the definition of the Jacobi Symbol and the corresponding properties of the Legendre symbol. Proofs may be easily found in the literature - for example in Ireland and Rosen "A Classical Introduction to Modern Number Theory". $\endgroup$ – Old John Oct 25 '13 at 19:53
  • 2
    $\begingroup$ @OldJohn Thanks for the information. I wonder why nobody has answered this question yet if they are immediate consequences of the corresponding properties of the Legendre symbol. $\endgroup$ – Makoto Kato Oct 26 '13 at 0:02
  • 3
    $\begingroup$ @SiddharthPrasad I had searched but had not found them. I'm not sure they are trivial for everybody. $\endgroup$ – Makoto Kato Feb 17 '14 at 2:55
9
$\begingroup$

1. Let $n$ be a positive odd integer. Let $a, b$ be integers such that $a \equiv b$ (mod $n$). Then $$\left(\frac{a}{n}\right) = \left(\frac{b}{n}\right)$$

Proof: Let $n = \prod p$ be the prime decomposition of $n$ with every prime factor repeated according to its multiplicity. Since $a \equiv b$ (mod $p$) for every prime factor of $n$, $\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$. Hence $\prod \left(\frac{a}{p}\right) = \prod \left(\frac{b}{p}\right)$. Hence $\prod \left(\frac{a}{n}\right) = \prod \left(\frac{b}{n}\right)$.

2. Let $a$ be integers. Let $m, n$ be positive odd integers. Then $$\left(\frac{a}{mn}\right) = \left(\frac{a}{m}\right)\left(\frac{a}{n}\right)$$

Proof: Clear from the definition of Jacobi symbol.

3. Let $a, b$ be integers. Let $n$ be a positive odd integer. Then $$\left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$$

Proof: Let $n = \prod p$ be the prime decomposition of $n$ as in the proof of $1.$ $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ for every prime factor $p$ of $n$. Hence $\prod \left(\frac{ab}{p}\right) = \prod \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$. Hence $\left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$.

Lemma 1 Let $a, b$ be odd integers. Then $(ab - 1)/2 \equiv (a - 1)/2 + (b - 1)/2$ (mod $2$).

Proof: Since $a - 1$ and $b - 1$ are even, $(a - 1)(b - 1) \equiv 0$ (mod $4$).

Hence $ab - a - b + 1 \equiv 0$ (mod $4$).

Hence $ab - 1 \equiv (a - 1) + (b - 1)$ (mod $4$).

Hence $(ab - 1)/2 \equiv (a - 1)/2 + (b - 1)/2$ (mod $2$).

Lemma 2 Let $a, b$ be odd integers. Then $(a^2b^2 - 1)/8 \equiv (a^2 - 1)/8 + (b^2 - 1)/8$ (mod $2$).

Proof:

$a^2 - 1 \equiv 0$ (mod $4$).

$b^2 - 1 \equiv 0$ (mod $4$).

Hence $(a^2 - 1)(b^2 - 1) \equiv 0$ (mod $16$).

Hence $a^2b^2 - a^2 - b^2 + 1 \equiv 0$ (mod $16$).

Hence $a^2b^2 - 1 \equiv (a^2 - 1) + (b^2 - 1)$ (mod $16$).

Hence $(a^2b^2 - 1)/8 \equiv (a^2 - 1)/8 + (b^2 - 1)/8$ (mod $2$).

Lemma 3 Let $a, b, c$ be positive odd integers. Suppose

$\left(\frac{a}{c}\right) \left(\frac{c}{a}\right) = (-1)^{\frac{a-1}{2}\frac{c-1}{2}}$.

$\left(\frac{b}{c}\right) \left(\frac{c}{b}\right) = (-1)^{\frac{b-1}{2}\frac{c-1}{2}}$.

Then $\left(\frac{ab}{c}\right) \left(\frac{c}{ab}\right) = (-1)^{\frac{ab-1}{2}\frac{c-1}{2}}$.

Proof: $\left(\frac{ab}{c}\right) \left(\frac{c}{ab}\right) =\left(\frac{a}{c}\right) \left(\frac{c}{a}\right)\left(\frac{b}{c}\right) \left(\frac{c}{b}\right) = (-1)^{\frac{a-1}{2}\frac{c-1}{2} + \frac{b-1}{2}\frac{c-1}{2}} = (-1)^{(\frac{a-1}{2} + \frac{b-1}{2})\frac{c-1}{2}} = (-1)^{\frac{ab-1}{2}\frac{c-1}{2}}$.

The first equality follows from $2.$ and $3.$ The last equality follows from Lemma 1.

4. Let $m, n$ be positive odd integers such that gcd$(m,n) = 1$. Then $$\left(\frac{m}{n}\right) \left(\frac{n}{m}\right) = (-1)^{\frac{m-1}{2}\frac{n-1}{2}}$$.

Proof: This follows immediately from Quadratic Reciprocity Theorem using Legendre symbol and Lemma 3.

5. Let $n$ be a positive odd integer. Then $$\left(\frac{-1}{n}\right) = (-1)^{\frac{n-1}{2}}$$.

Proof: This follows immediately from the first supplementary law of quadratic reciprocity using Legendre symbol and $2.$ and Lemma 1.

6. Let $n$ be a positive odd integer. Then $$\left(\frac{2}{n}\right) = (-1)^{\frac{n^2-1}{8}}$$.

Proof: This follows immediately from the second supplementary law of quadratic reciprocity using Legendre symbol and $2.$ and Lemma 2.

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