7
$\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$
4
  • 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
    Commented Oct 25, 2013 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
    Commented Oct 25, 2013 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$ Commented Oct 26, 2013 at 0:02
  • 3
    $\begingroup$ @SiddharthPrasad I had searched but had not found them. I'm not sure they are trivial for everybody. $\endgroup$ Commented Feb 17, 2014 at 2:55

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .