Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

5.7: Jacobi Symbol

( \newcommand{\kernel}{\mathrm{null}\,}\)

In this section, we define the Jacobi symbol which is a generalization of the Legendre symbol. The Legendre symbol was defined in terms of primes, while Jacobi symbol will be generalized for any odd integers and it will be given in terms of Legendre symbol.

Let n be an odd positive integer with prime factorization

n=pa11pa22...pamm

and let a be an integer relatively prime to n, then

(an)=mi=1(api)ci.

Notice that from the prime factorization of 45, we get that (255)=(25)(211)=(1)(1)=1

We now prove some properties for Jacobi symbol that are similar to the properties of Legendre symbol.

properties for Jacobi symbol

Let n be an odd positive integer and let a and b be integers such that(a,n)=1 and (b,n)=1. Then

  1. if n(ab), then (an)=(bn).
  2. (abn)=(an)(bn).

Proofs

Proof of 1

Note that if p is in the prime factorization of n, then we have that p(ab). Hence by Theorem 70, we get that

(ap)=(bp).

As a result, we have

(an)=mi=1(api)ci=mi=1(bpi)ci

Proof of 2

Note that by Theorem 71, we have (abp)=(ap)(bp) for any prime p appearing in the prime factorization of n. As a result, we have

(abn)=mi=1(abpi)ci=mi=1(api)cimi=1(bpi)ci=(an)(bn).

In the following theorem, we determine (1n) and (2n).

Note

Let n be an odd positive integer. Then

  1. (1n)=(1)(n1)/2.
  2. (2n)=(1)(n21)/8.

Proofs

Proof of 1

If p is in the prime factorization of n, then by Corollary 3, we see that (1p)=(1)(p1)/2. Thus

(1n)=mi=1(1pi)ci=(1)mi=1ci(pi1)/2.

Notice that since pi1 is even, we have

paii=(1+(pi1))ci1+ci(pi1)(mod 4)

and hence we get

n=mi=1pcii1+mi=1ci(pi1)(mod 4).

As a result, we have (n1)/2mi=1ci(pi1)/2 (mod 2).

Proof of 2

If p is a prime, then by Theorem 72 we have

(2p)=(1)(p21)/8. Hence (2n)=(1)mi=1ci(p2i1)/8.

Because 8p2i1, we see similarly that

(1+(p2i1))ci1+ci(p2i1)(mod 64) and thus n21+mi=1ci(p2i1)(mod 64),

which implies that

(n21)/8mi=1ci(p2i1)/8(mod 8).

We now show that the reciprocity law holds for Jacobi symbol.

Let (a,b)=1 be odd positive integers. Then

(ba)(ab)=(1)a12.b12.

Notice that since a=mj=1pcii and b=ni=1qdii we get

(ba)(ab)=ni=1mj=1[(pjqi)(qipj)]cjdi

By the law of quadratic reciprocity, we get

(ba)(ab)=(1)ni=1mj=1cj(pj12)di(qi12)

As in the proof of part 1 of Theorem 75, we see that

mj=1cj(pj12)a12(mod 2)

and

ni=1di(qi12)b12(mod 2).

Thus we conclude that

mj=1cj(pj12)ni=1di(qi12)a12.b12(mod 2).

Exercises

  1. Evaluate (2584520).
  2. Evaluate (10082307).
  3. For which positive integers n that are relatively prime to 15 does the Jacobi symbol (15n) equal 1?
  4. Let n be an odd square free positive integer. Show that there is an integer a such that (a,n)=1 and (an)=1.

Contributors and Attributions

  • Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.


This page titled 5.7: Jacobi Symbol is shared under a CC BY license and was authored, remixed, and/or curated by Wissam Raji.

Support Center

How can we help?