Generalization of the Legendre symbol in number theory
In algebraic number theory and related branches of mathematics the Jacobi symbol
(
a
m
)
{\displaystyle \left({\tfrac {a}{m}}\right)}
a
{\displaystyle a}
m
.
{\displaystyle m.}
[1]
m
=
p
1
p
2
…
{\displaystyle m=p_{1}p_{2}\dots }
p
i
{\displaystyle p_{i}}
[2] Legendre symbols
(
a
m
)
=
(
a
p
1
)
(
a
p
2
)
…
{\displaystyle \left({\frac {a}{m}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)\dots }
(
a
1
)
{\displaystyle \left({\frac {a}{1}}\right)}
1.
{\displaystyle 1.}
Properties of the Jacobi symbol
edit
The Legendre symbol
(
a
p
)
{\displaystyle \left({\tfrac {a}{p}}\right)}
a
{\displaystyle a}
p
{\displaystyle p}
(
a
p
)
=
{
0
if
a
≡
0
(
mod
p
)
,
1
if
a
≢
0
(
mod
p
)
and for some integer
x
:
a
≡
x
2
(
mod
p
)
,
−
1
if
a
≢
0
(
mod
p
)
and there is no such
x
.
{\displaystyle \left({\frac {a}{p}}\right)=\left\{{\begin{array}{rl}0&{\text{if }}a\equiv 0{\pmod {p}},\\1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and for some integer }}x\colon \;a\equiv x^{2}{\pmod {p}},\\-1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and there is no such }}x.\end{array}}\right.}
The properties of the Jacobi symbol are derived from those of the Legendre symbol.[3]
Since
(
a
1
a
2
p
)
=
(
a
1
p
)
(
a
2
p
)
{\displaystyle \left({\tfrac {a_{1}a_{2}}{p}}\right)=\left({\tfrac {a_{1}}{p}}\right)\left({\tfrac {a_{2}}{p}}\right)}
(
a
1
a
2
m
)
=
(
a
1
m
)
(
a
2
m
)
.
{\displaystyle \left({\tfrac {a_{1}a_{2}}{m}}\right)=\left({\tfrac {a_{1}}{m}}\right)\left({\tfrac {a_{2}}{m}}\right).}
Obviously from the definition
(
a
m
1
m
2
)
=
(
a
m
1
)
(
a
m
2
)
.
{\displaystyle \left({\tfrac {a}{m_{1}m_{2}}}\right)=\left({\tfrac {a}{m_{1}}}\right)\left({\tfrac {a}{m_{2}}}\right).}
These imply that
(
a
b
2
m
)
=
(
a
m
)
{\displaystyle \left({\tfrac {ab^{2}}{m}}\right)=\left({\tfrac {a}{m}}\right)}
(
a
m
n
2
)
=
(
a
m
)
.
{\displaystyle \left({\tfrac {a}{mn^{2}}}\right)=\left({\tfrac {a}{m}}\right).}
If
a
1
≡
a
2
(
mod
m
)
{\displaystyle a_{1}\equiv a_{2}{\pmod {m}}}
a
1
≡
a
2
(
mod
p
)
{\displaystyle a_{1}\equiv a_{2}{\pmod {p}}}
p
{\displaystyle p}
(
a
1
p
)
=
(
a
2
p
)
{\displaystyle \left({\tfrac {a_{1}}{p}}\right)=\left({\tfrac {a_{2}}{p}}\right)}
(
a
1
m
)
=
(
a
2
m
)
.
{\displaystyle \left({\tfrac {a_{1}}{m}}\right)=\left({\tfrac {a_{2}}{m}}\right).}
If
gcd
(
a
,
m
)
>
1
{\displaystyle \gcd(a,m)>1}
p
{\displaystyle p}
a
,
{\displaystyle a,\;}
(
a
p
)
=
0
{\displaystyle \left({\tfrac {a}{p}}\right)=0}
(
a
m
)
=
0.
{\displaystyle \left({\tfrac {a}{m}}\right)=0.}
If
gcd
(
a
,
m
)
=
1
{\displaystyle \gcd(a,m)=1}
(
a
p
)
=
±
1
{\displaystyle \left({\tfrac {a}{p}}\right)=\pm 1}
(
a
m
)
=
±
1
{\displaystyle \left({\tfrac {a}{m}}\right)=\pm 1}
Differences between Legendre and Jacobi symbols
edit
(
a
m
)
=
1
{\displaystyle \left({\tfrac {a}{m}}\right)=1}
m
{\displaystyle m}
a
{\displaystyle a}
mod
m
{\displaystyle {\bmod {m}}}
m
{\displaystyle m}
Euler's criterion is not true for composite
m
{\displaystyle m}
(
2
15
)
=
1
{\displaystyle \left({\tfrac {2}{15}}\right)=1}
[4]
2
7
≡
8
(
mod
15
)
.
{\displaystyle 2^{7}\equiv 8{\pmod {15}}.}
uses , below.
Quadratic reciprocity
edit
Let
m
=
p
1
p
2
⋯
q
1
q
2
…
{\displaystyle m=p_{1}p_{2}\cdots q_{1}q_{2}\dots }
p
i
≡
1
(
mod
4
)
{\displaystyle p_{i}\equiv 1{\pmod {4}}}
q
i
≡
3
(
mod
4
)
{\displaystyle q_{i}\equiv 3{\pmod {4}}}
(
−
1
p
)
=
1
{\displaystyle \left({\tfrac {-1}{p}}\right)=1}
(
−
1
q
)
=
−
1.
{\displaystyle \left({\tfrac {-1}{q}}\right)=-1.}
m
≡
3
(
mod
4
)
{\displaystyle m\equiv 3{\pmod {4}}}
q
i
{\displaystyle q_{i}}
Likewise
(
−
1
m
)
=
(
−
1
p
1
)
(
−
1
p
2
)
⋯
(
−
1
q
1
)
(
−
1
q
2
)
…
{\displaystyle \left({\tfrac {-1}{m}}\right)=\left({\tfrac {-1}{p_{1}}}\right)\left({\tfrac {-1}{p_{2}}}\right)\cdots \left({\tfrac {-1}{q_{1}}}\right)\left({\tfrac {-1}{q_{2}}}\right)\dots }
−
1
{\displaystyle -1}
q
i
{\displaystyle q_{i}}
(
−
1
m
)
=
{
1
if
m
≡
1
(
mod
4
)
−
1
if
m
≡
3
(
mod
4
)
{\displaystyle \left({\frac {-1}{m}}\right)={\begin{cases}1&{\text{if }}m\equiv 1{\pmod {4}}\\-1&{\text{if }}m\equiv 3{\pmod {4}}\end{cases}}}
which is equivalent to
(
−
1
m
)
=
(
−
1
)
m
−
1
2
.
{\displaystyle \left({\frac {-1}{m}}\right)=(-1)^{\tfrac {m-1}{2}}.}
Let
m
=
p
1
p
2
⋯
q
1
q
2
…
{\displaystyle m=p_{1}p_{2}\cdots q_{1}q_{2}\dots }
p
i
≡
±
1
(
mod
8
)
{\displaystyle p_{i}\equiv \pm 1{\pmod {8}}}
q
i
≡
±
3
(
mod
8
)
{\displaystyle q_{i}\equiv \pm 3{\pmod {8}}}
(
2
p
)
=
1
{\displaystyle \left({\tfrac {2}{p}}\right)=1}
(
2
q
)
=
−
1.
{\displaystyle \left({\tfrac {2}{q}}\right)=-1.}
m
≡
±
3
(
mod
8
)
{\displaystyle m\equiv \pm 3{\pmod {8}}}
q
i
{\displaystyle q_{i}}
Likewise
(
2
m
)
=
(
2
p
1
)
(
2
p
2
)
⋯
(
2
q
1
)
(
2
q
2
)
…
{\displaystyle \left({\tfrac {2}{m}}\right)=\left({\tfrac {2}{p_{1}}}\right)\left({\tfrac {2}{p_{2}}}\right)\cdots \left({\tfrac {2}{q_{1}}}\right)\left({\tfrac {2}{q_{2}}}\right)\dots }
−
1
{\displaystyle -1}
q
i
{\displaystyle q_{i}}
(
2
m
)
=
{
1
if
m
≡
1
,
7
≡
0
±
1
(
mod
8
)
−
1
if
m
≡
3
,
5
≡
4
±
1
(
mod
8
)
{\displaystyle \left({\frac {2}{m}}\right)={\begin{cases}1&{\text{if }}m\equiv 1,7\;\;\equiv 0\pm 1{\pmod {8}}\\-1&{\text{if }}m\equiv 3,5\;\;\equiv 4\pm 1{\pmod {8}}\end{cases}}}
which is equivalent to
(
2
m
)
=
(
−
1
)
m
2
−
1
8
.
{\displaystyle \left({\frac {2}{m}}\right)=(-1)^{\tfrac {m^{2}-1}{8}}.}
Combining with the first supplement gives
(
−
2
m
)
=
{
1
if
m
≡
1
,
3
≡
2
±
1
(
mod
8
)
−
1
if
m
≡
5
,
7
≡
6
±
1
(
mod
8
)
{\displaystyle \left({\frac {-2}{m}}\right)={\begin{cases}1&{\text{if }}m\equiv 1,3\;\;\equiv 2\pm 1{\pmod {8}}\\-1&{\text{if }}m\equiv 5,7\;\;\equiv 6\pm 1{\pmod {8}}\end{cases}}}
which is equivalent to
(
−
2
m
)
=
(
−
1
)
(
m
+
2
)
2
−
1
8
.
{\displaystyle \left({\frac {-2}{m}}\right)=(-1)^{\tfrac {(m+2)^{2}-1}{8}}.}
a
{\displaystyle a}
Let
m
=
p
1
p
2
⋯
q
1
q
2
⋯
{\displaystyle m=p_{1}p_{2}\cdots q_{1}q_{2}\cdots }
p
i
≡
1
(
mod
4
)
{\displaystyle p_{i}\equiv 1{\pmod {4}}}
q
i
≡
3
(
mod
4
)
{\displaystyle q_{i}\equiv 3{\pmod {4}}}
In the same way let
a
=
b
1
b
2
⋯
c
1
c
2
⋯
{\displaystyle a=b_{1}b_{2}\cdots c_{1}c_{2}\cdots }
b
i
{\displaystyle b_{i}}
c
i
{\displaystyle c_{i}}
b
i
≡
1
(
mod
4
)
{\displaystyle b_{i}\equiv 1{\pmod {4}}}
c
i
≡
3
(
mod
4
)
{\displaystyle c_{i}\equiv 3{\pmod {4}}}
The values of the inverted Legendre symbols are known:
(
b
p
)
=
(
p
b
)
,
(
c
p
)
=
(
p
c
)
,
(
b
q
)
=
(
q
b
)
,
(
c
q
)
=
−
(
q
c
)
{\displaystyle \left({\tfrac {b}{p}}\right)=\left({\tfrac {p}{b}}\right),\;\left({\tfrac {c}{p}}\right)=\left({\tfrac {p}{c}}\right),\;\left({\tfrac {b}{q}}\right)=\left({\tfrac {q}{b}}\right),\;\left({\tfrac {c}{q}}\right)=-\left({\tfrac {q}{c}}\right)}
m
≡
3
(
mod
4
)
{\displaystyle m\equiv 3{\pmod {4}}}
q
i
{\displaystyle q_{i}}
a
≡
3
(
mod
4
)
{\displaystyle a\equiv 3{\pmod {4}}}
c
i
{\displaystyle c_{i}}
(
a
m
)
=
(
a
p
1
)
(
a
p
2
)
⋯
(
a
q
1
)
(
a
q
2
)
…
=
(
b
1
⋯
c
1
⋯
p
1
)
(
b
1
⋯
c
1
⋯
p
2
)
⋯
(
b
1
⋯
c
1
⋯
q
1
)
…
=
(
b
1
p
1
)
⋯
(
c
1
p
1
)
⋯
(
b
1
p
2
)
⋯
(
c
1
p
2
)
⋯
(
b
1
q
1
)
⋯
(
c
1
q
1
)
…
=
±
(
p
1
b
1
)
⋯
(
p
1
c
1
)
⋯
(
p
2
b
1
)
⋯
(
p
2
c
1
)
⋯
(
q
1
b
1
)
⋯
(
q
1
c
1
)
…
=
±
(
p
1
b
1
)
(
p
2
b
1
)
⋯
(
q
1
b
1
)
⋯
(
p
1
b
2
)
(
p
2
b
2
)
⋯
(
q
1
b
2
)
…
=
±
(
p
1
p
2
⋯
q
1
⋯
b
1
)
(
p
1
p
2
⋯
q
1
⋯
b
2
)
⋯
(
p
1
p
2
⋯
q
1
⋯
c
1
)
…
=
±
(
m
b
1
)
(
m
b
2
)
⋯
(
m
c
1
)
…
=
±
(
m
a
)
.
{\displaystyle {\begin{aligned}\left({\frac {a}{m}}\right)&=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)\cdots \left({\frac {a}{q_{1}}}\right)\left({\frac {a}{q_{2}}}\right)\dots \\&=\left({\frac {b_{1}\cdots c_{1}\cdots }{p_{1}}}\right)\left({\frac {b_{1}\cdots c_{1}\cdots }{p_{2}}}\right)\cdots \left({\frac {b_{1}\cdots c_{1}\cdots }{q_{1}}}\right)\dots \\&=\left({\frac {b_{1}}{p_{1}}}\right)\cdots \left({\frac {c_{1}}{p_{1}}}\right)\cdots \left({\frac {b_{1}}{p_{2}}}\right)\cdots \left({\frac {c_{1}}{p_{2}}}\right)\cdots \left({\frac {b_{1}}{q_{1}}}\right)\cdots \left({\frac {c_{1}}{q_{1}}}\right)\dots \\&=\pm \left({\frac {p_{1}}{b_{1}}}\right)\cdots \left({\frac {p_{1}}{c_{1}}}\right)\cdots \left({\frac {p_{2}}{b_{1}}}\right)\cdots \left({\frac {p_{2}}{c_{1}}}\right)\cdots \left({\frac {q_{1}}{b_{1}}}\right)\cdots \left({\frac {q_{1}}{c_{1}}}\right)\dots \\&=\pm \left({\frac {p_{1}}{b_{1}}}\right)\left({\frac {p_{2}}{b_{1}}}\right)\cdots \left({\frac {q_{1}}{b_{1}}}\right)\cdots \left({\frac {p_{1}}{b_{2}}}\right)\left({\frac {p_{2}}{b_{2}}}\right)\cdots \left({\frac {q_{1}}{b_{2}}}\right)\dots \\&=\pm \left({\frac {p_{1}p_{2}\cdots q_{1}\cdots }{b_{1}}}\right)\left({\frac {p_{1}p_{2}\cdots q_{1}\cdots }{b_{2}}}\right)\cdots \left({\frac {p_{1}p_{2}\cdots q_{1}\cdots }{c_{1}}}\right)\dots \\&=\pm \left({\frac {m}{b_{1}}}\right)\left({\frac {m}{b_{2}}}\right)\cdots \left({\frac {m}{c_{1}}}\right)\dots \\&=\pm \left({\frac {m}{a}}\right).\end{aligned}}}
The sign is negative if and only if the number of
c
i
q
j
{\displaystyle c_{i}q_{j}}
q
i
{\displaystyle q_{i}}
c
j
{\displaystyle c_{j}}
(
a
m
)
=
{
(
m
a
)
if
m
≡
1
(
mod
4
)
or
a
≡
1
(
mod
4
)
−
(
m
a
)
if
m
≡
3
(
mod
4
)
and
a
≡
3
(
mod
4
)
{\displaystyle \left({\frac {a}{m}}\right)={\begin{cases}\;\;\;\left({\frac {m}{a}}\right)&{\text{if }}m\equiv 1{\pmod {4}}{\text{ or }}a\equiv 1{\pmod {4}}\\-\left({\frac {m}{a}}\right)&{\text{if }}m\equiv 3{\pmod {4}}{\text{ and }}a\equiv 3{\pmod {4}}\end{cases}}}
which is equivalent to
(
a
m
)
=
(
m
a
)
(
−
1
)
m
−
1
2
a
−
1
2
.
{\displaystyle \left({\frac {a}{m}}\right)=\left({\frac {m}{a}}\right)(-1)^{{\tfrac {m-1}{2}}{\tfrac {a-1}{2}}}.}
a
{\displaystyle a}
Define the
∗
{\displaystyle ^{*}}
m
{\displaystyle m}
m
∗
=
{
m
if
m
≡
1
(
mod
4
)
−
m
if
m
≡
3
(
mod
4
)
.
{\displaystyle m^{*}={\begin{cases}\;\;\;m&{\text{if }}m\equiv 1{\pmod {4}}\\-m&{\text{if }}m\equiv 3{\pmod {4}}.\end{cases}}}
This operator is multiplicative
(
a
b
)
∗
=
a
∗
b
∗
.
{\displaystyle (ab)^{*}=a^{*}b^{*}.}
Let
m
=
p
1
p
2
⋯
{\displaystyle m=p_{1}p_{2}\cdots }
a
=
b
1
b
2
⋯
{\displaystyle a=b_{1}b_{2}\cdots }
For every Legendre symbol in the product it is known that
(
b
p
)
=
(
p
∗
b
)
.
{\displaystyle \left({\tfrac {b}{p}}\right)=\left({\tfrac {p^{*}}{b}}\right).}
(
a
m
)
=
(
a
p
1
)
(
a
p
2
)
⋯
=
(
b
1
b
2
⋯
p
1
)
(
b
1
b
2
⋯
p
2
)
⋯
=
(
b
1
p
1
)
(
b
2
p
1
)
⋯
(
b
1
p
2
)
(
b
2
p
2
)
⋯
=
(
p
1
∗
b
1
)
(
p
1
∗
b
2
)
⋯
(
p
2
∗
b
1
)
(
p
2
∗
b
2
)
⋯
=
(
p
1
∗
b
1
)
(
p
2
∗
b
1
)
⋯
(
p
1
∗
b
2
)
(
p
2
∗
b
2
)
⋯
=
(
p
1
∗
p
2
∗
⋯
b
1
)
(
p
1
∗
p
2
∗
⋯
b
2
)
⋯
=
(
m
∗
b
1
)
(
m
∗
b
2
)
⋯
=
(
m
∗
a
)
.
{\displaystyle {\begin{aligned}\left({\frac {a}{m}}\right)&=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)\cdots \\&=\left({\frac {b_{1}b_{2}\cdots }{p_{1}}}\right)\left({\frac {b_{1}b_{2}\cdots }{p_{2}}}\right)\cdots \\&=\left({\frac {b_{1}}{p_{1}}}\right)\left({\frac {b_{2}}{p_{1}}}\right)\cdots \left({\frac {b_{1}}{p_{2}}}\right)\left({\frac {b_{2}}{p_{2}}}\right)\cdots \\&=\left({\frac {p_{1}^{*}}{b_{1}}}\right)\left({\frac {p_{1}^{*}}{b_{2}}}\right)\cdots \left({\frac {p_{2}^{*}}{b_{1}}}\right)\left({\frac {p_{2}^{*}}{b_{2}}}\right)\cdots \\&=\left({\frac {p_{1}^{*}}{b_{1}}}\right)\left({\frac {p_{2}^{*}}{b_{1}}}\right)\cdots \left({\frac {p_{1}^{*}}{b_{2}}}\right)\left({\frac {p_{2}^{*}}{b_{2}}}\right)\cdots \\&=\left({\frac {p_{1}^{*}p_{2}^{*}\cdots }{b_{1}}}\right)\left({\frac {p_{1}^{*}p_{2}^{*}\cdots }{b_{2}}}\right)\cdots \\&=\left({\frac {m^{*}}{b_{1}}}\right)\left({\frac {m^{*}}{b_{2}}}\right)\cdots \\&=\left({\frac {m^{*}}{a}}\right).\end{aligned}}}
Gauss's lemma extends to Jacobi symbols. Let
m
>
0
{\displaystyle m>0}
I
=
{
i
:
1
≤
i
≤
m
−
1
2
}
{\displaystyle I=\{i:1\leq i\leq {\tfrac {m-1}{2}}\}}
−
I
=
{
−
j
:
j
∈
I
}
{\displaystyle -I=\{-j:j\in I\}}
(
Z
/
m
Z
)
=
I
∪
−
I
∪
{
0
}
{\displaystyle (\mathbb {Z} /m\mathbb {Z} )=I\cup -I\cup \{0\}}
a
∈
I
,
gcd
(
a
,
m
)
=
1
{\displaystyle a\in I,\gcd(a,m)=1}
t
=
#
{
j
∈
I
:
a
j
∈
−
I
}
{\displaystyle t=\#\{j\in I:aj\in -I\}}
Then
(
a
m
)
=
(
−
1
)
t
{\displaystyle \left({\frac {a}{m}}\right)=(-1)^{t}}
Zolotarev's lemma extends to Jacobi symbols. For
a
∈
(
Z
/
m
Z
)
×
{\displaystyle a\in (\mathbb {Z} /m\mathbb {Z} )^{\times }}
π
a
{\displaystyle \pi _{a}}
(
Z
/
m
Z
)
{\displaystyle (\mathbb {Z} /m\mathbb {Z} )}
a
{\displaystyle a}
signature of this permutation is the Jacobi symbol:
(
a
m
)
=
ε
(
π
a
)
{\displaystyle \left({\frac {a}{m}}\right)=\varepsilon (\pi _{a})}
See here for details and an example.
Calculating the Jacobi symbol
edit
The expression
a
mod
b
{\displaystyle a{\bmod {b}}}
x
{\displaystyle x}
x
≡
a
(
mod
b
)
{\displaystyle x\equiv a{\pmod {b}}}
|
x
|
<
|
b
|
.
{\displaystyle |x|<|b|.}
[5]
Repeat these steps until
a
{\displaystyle a}
1) if
a
{\displaystyle a}
(
a
m
)
=
(
−
1
m
)
(
|
a
|
m
)
{\displaystyle \left({\tfrac {a}{m}}\right)=\left({\tfrac {-1}{m}}\right)\left({\tfrac {|a|}{m}}\right)}
m
≡
3
(
mod
4
)
{\displaystyle m\equiv 3{\pmod {4}}}
2) If
a
{\displaystyle a}
a
{\displaystyle a}
In the latter case
(
2
a
m
)
=
(
2
m
)
(
a
m
)
{\displaystyle \left({\tfrac {2a}{m}}\right)=\left({\tfrac {2}{m}}\right)\left({\tfrac {a}{m}}\right)}
m
≡
±
3
(
mod
8
)
{\displaystyle m\equiv \pm 3{\pmod {8}}}
3) If
a
{\displaystyle a}
(
a
m
)
=
(
−
1
)
m
−
1
2
a
−
1
2
(
m
mod
a
a
)
{\displaystyle \left({\tfrac {a}{m}}\right)=(-1)^{{\tfrac {m-1}{2}}{\tfrac {a-1}{2}}}\left({\tfrac {m{\bmod {a}}}{a}}\right)}
m
≡
3
(
mod
4
)
{\displaystyle m\equiv 3{\pmod {4}}}
a
≡
3
(
mod
4
)
{\displaystyle a\equiv 3{\pmod {4}}}
A few examples:
(
−
24
5
)
=
(
−
1
5
)
(
24
5
)
=
(
24
5
)
=
(
8
5
)
(
3
5
)
=
(
2
5
)
(
3
5
)
−
(
3
5
)
=
−
(
2
3
)
=
1
{\displaystyle \left({\tfrac {-24}{5}}\right)=\left({\tfrac {-1}{5}}\right)\left({\tfrac {24}{5}}\right)=\left({\tfrac {24}{5}}\right)=\left({\tfrac {8}{5}}\right)\left({\tfrac {3}{5}}\right)=\left({\tfrac {2}{5}}\right)\left({\tfrac {3}{5}}\right)-\left({\tfrac {3}{5}}\right)=-\left({\tfrac {2}{3}}\right)=1}
(
−
24
7
)
=
(
−
1
7
)
(
24
7
)
=
−
(
24
7
)
=
−
(
8
7
)
(
3
7
)
=
−
(
2
7
)
(
3
7
)
=
−
(
3
7
)
=
(
4
3
)
=
1
{\displaystyle \left({\tfrac {-24}{7}}\right)=\left({\tfrac {-1}{7}}\right)\left({\tfrac {24}{7}}\right)=-\left({\tfrac {24}{7}}\right)=-\left({\tfrac {8}{7}}\right)\left({\tfrac {3}{7}}\right)=-\left({\tfrac {2}{7}}\right)\left({\tfrac {3}{7}}\right)=-\left({\tfrac {3}{7}}\right)=\left({\tfrac {4}{3}}\right)=1}
Calculating the Jacobi symbol is similar to computing the gcd using the Euclidean algorithm .
Euclid
(
a
,
b
)
{\displaystyle \operatorname {Euclid} (a,b)}
if
(
a
≤
0
or
b
≤
0
)
fail
{\displaystyle \operatorname {if} \;(a\leq 0\;\operatorname {or} \;b\leq 0)\operatorname {fail} }
if
(
a
=
b
)
return
a
{\displaystyle \operatorname {if} \;(a=b)\operatorname {return} a}
return
Euclid
(
b
mod
a
,
a
)
{\displaystyle \operatorname {return} \operatorname {Euclid} (b{\bmod {a}},a)}
end
Euclid
{\displaystyle \operatorname {end} \operatorname {Euclid} }
Jacobi
(
a
,
m
)
{\displaystyle \operatorname {Jacobi} (a,m)}
if
(
m
<
0
or
m
≡
0
(
mod
2
)
)
{\displaystyle \operatorname {if} \;(m<0\;\operatorname {or} \;m\equiv 0{\pmod {2}})}
fail
{\displaystyle \operatorname {fail} }
if
(
a
=
0
)
{\displaystyle \operatorname {if} \;(a=0)}
return
0
{\displaystyle \operatorname {return} 0}
if
(
a
=
1
)
{\displaystyle \operatorname {if} \;(a=1)}
return
1
{\displaystyle \operatorname {return} 1}
Examine the bits in
a
{\displaystyle a}
a
=
s
2
k
a
′
{\displaystyle a=s2^{k}a'}
s
=
±
1
,
k
≥
0
,
a
′
>
0
,
a
′
≡
1
(
mod
2
)
.
{\displaystyle s=\pm 1,\;k\geq 0,\;a'>0,\;a'\equiv 1{\pmod {2}}.}
if
(
s
<
0
and
m
≡
3
(
mod
4
)
)
{\displaystyle \operatorname {if} \;(s<0\operatorname {and} m\equiv 3{\pmod {4}})}
return
−
Jacobi
(
2
k
a
′
,
m
)
{\displaystyle \operatorname {return} -\operatorname {Jacobi} (2^{k}a',m)}
if
(
k
≡
1
(
mod
2
)
and
m
≡
±
3
(
mod
8
)
)
{\displaystyle \operatorname {if} \;(k\equiv 1{\pmod {2}}\operatorname {and} m\equiv \pm 3{\pmod {8}})}
return
−
Jacobi
(
a
′
,
m
)
{\displaystyle \operatorname {return} -\operatorname {Jacobi} (a',m)}
if
(
a
′
≡
3
(
mod
4
)
and
m
≡
3
(
mod
4
)
)
{\displaystyle \operatorname {if} \;(a'\equiv 3{\pmod {4}}\operatorname {and} m\equiv 3{\pmod {4}})}
return
−
Jacobi
(
m
mod
a
′
,
a
′
)
{\displaystyle \operatorname {return} -\operatorname {Jacobi} (m{\bmod {a}}',a')}
return
Jacobi
(
m
mod
a
′
,
a
′
)
{\displaystyle \operatorname {return} \operatorname {Jacobi} (m{\bmod {a}}',a')}
end
Jacobi
{\displaystyle \operatorname {end} \operatorname {Jacobi} }
[
a
b
]
{\displaystyle [{\tfrac {a}{b}}]}
[6]
[
13
21
]
=
[
8
13
]
=
[
5
8
]
=
[
3
5
]
=
[
2
3
]
=
[
1
2
]
=
1
{\displaystyle [{\tfrac {13}{21}}]=[{\tfrac {8}{13}}]=[{\tfrac {5}{8}}]=[{\tfrac {3}{5}}]=[{\tfrac {2}{3}}]=[{\tfrac {1}{2}}]=1}
Lamé’s Theorem (1844) states that the number of
mod
{\displaystyle \operatorname {mod} }
[7]
mod
{\displaystyle \operatorname {mod} }
So, for example 2000-digit numbers will require about twice as many
mod
{\displaystyle \operatorname {mod} }
mod
{\displaystyle \operatorname {mod} }
The algorithm is well-suited to machine calculations since its running time is
O
(
min
(
log
a
,
log
m
)
)
{\displaystyle O(\min(\log a,\log m))}
[8] [9]
function jacobi ( a , m )
assert ( m > 0 and m % 2 == 1 , "m must be positive and odd" )
local t = 1 -- returned value
while true do
if a == 1 then
return t -- success t is the Jacobi symbol
elseif a == 0 then
return 0 -- a and m were not relatively prime
end
if a < 0 then
a = - a -- if a is negative set a = |a|
if m % 4 == 3 then -- and evaluate (-1|m)
t = - t
end
end
-- a is positive
local p = 0 -- power of 2 dividing a
while a % 2 == 0 do
p = p + 1
a = a / 2
end
if p % 2 == 1 then -- if the power of 2 is odd
if m % 8 == 3 or m % 8 == 5 then -- evaluate (2|m)
t = - t
end
end
-- a is odd
if m % 4 == 3 and a % 4 == 3 then -- does inverting the symbol
t = - t -- change its sign?
end
local temp = a -- next iteration is (m mod a|a)
a = m % a
m = temp
end
int jacobi ( int a , int m ) {
assert ( m > 0 && m % 2 == 1 );
int t = 1 ; // return value (accumulated sign)
while ( 1 ) {
if ( a == 1 ) return t ; // success
if ( a == 0 ) return 0 ; // a and m were not coprime
if ( a < 0 ) { // if a is negative replace it with the absolute value
a = - a ; // and evaluate (-1|m)
if ( m % 4 == 3 ) t = - t ;
} // a is positive
int p = 0 ; // power of 2 dividing a
while ( a % 2 == 0 ) {
a /= 2 ;
p ++ ;
} // a is odd
if ( p % 2 == 1 ) // if the power of 2 was odd
if ( m % 8 == 3 || m % 8 == 5 ) t = - t ; // evaluate (2|m)
if ( m % 4 == 3 && a % 4 == 3 ) t = - t ; // evaluate (m|a)
int temp = a ; // next iteration is m mod a over a
a = m % a ;
m = temp ;
}
}
The Jacobi symbol is of theoretical interest in number theory ,[10] computational .[11] Cryptography in particular uses large prime numbers. A number of primality testing and integer factorization algorithms take advantage of the fact that Jacobi symbols can be computed quickly.
Because Euler's criterion is not valid for composite
m
{\displaystyle m}
a
{\displaystyle a}
(
a
m
)
{\displaystyle \left({\tfrac {a}{m}}\right)}
(
a
m
)
≢
a
m
−
1
2
(
mod
m
)
{\displaystyle \left({\tfrac {a}{m}}\right)\not \equiv a^{\tfrac {m-1}{2}}{\pmod {m}}}
m
{\displaystyle m}
Solovay–Strassen primality test . In some algorithms, such as the Lucas–Lehmer primality test , the value of certain Jacobi symbols is known theoretically[12] [13]
An example of a factoring algorithm that uses Jacobi symbols is the continued fraction algorithm [14]
N
{\displaystyle N}
x
2
≡
y
2
(
mod
N
)
{\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}
The Legendre symbol was introduced in 1798. It is not practical for calculations because it requires factorization into primes before it can be inverted. Jacobi introduced his symbol in 1837.[15] here Gauss' first proof of quadratic reciprocity[16] [17] [18]
( k / n ) for 1≤ k ≤ 30, 1≤ n ≤ 59, n odd.
k
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
− 1
1
1
− 1
1
1
1
1
− 1
1
1
1
1
1
1
− 1
1
1
1
1
1
1
1
1
− 1
1
1
1
1
1
3
1
−1
0
1
−1
0
1
−1
0
1
−1
0
1
−1
0
1
−1
0
1
−1
0
1
−1
0
1
−1
0
1
−1
0
5
1
−1
−1
1
0
1
−1
−1
1
0
1
−1
−1
1
0
1
−1
−1
1
0
1
−1
−1
1
0
1
−1
−1
1
0
7
1
1
−1
1
−1
−1
0
1
1
−1
1
−1
−1
0
1
1
−1
1
−1
−1
0
1
1
−1
1
−1
−1
0
1
1
9
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
1
1
0
11
1
−1
1
1
1
−1
−1
−1
1
−1
0
1
−1
1
1
1
−1
−1
−1
1
−1
0
1
−1
1
1
1
−1
−1
−1
13
1
−1
1
1
−1
−1
−1
−1
1
1
−1
1
0
1
−1
1
1
−1
−1
−1
−1
1
1
−1
1
0
1
−1
1
1
15
1
1
0
1
0
0
−1
1
0
0
−1
0
−1
−1
0
1
1
0
1
0
0
−1
1
0
0
−1
0
−1
−1
0
17
1
1
−1
1
−1
−1
−1
1
1
−1
−1
−1
1
−1
1
1
0
1
1
−1
1
−1
−1
−1
1
1
−1
−1
−1
1
19
1
−1
−1
1
1
1
1
−1
1
−1
1
−1
−1
−1
−1
1
1
−1
0
1
−1
−1
1
1
1
1
−1
1
−1
1
21
1
−1
0
1
1
0
0
−1
0
−1
−1
0
−1
0
0
1
1
0
−1
1
0
1
−1
0
1
1
0
0
−1
0
23
1
1
1
1
−1
1
−1
1
1
−1
−1
1
1
−1
−1
1
−1
1
−1
−1
−1
−1
0
1
1
1
1
−1
1
−1
25
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
1
1
1
1
0
27
1
−1
0
1
−1
0
1
−1
0
1
−1
0
1
−1
0
1
−1
0
1
−1
0
1
−1
0
1
−1
0
1
−1
0
29
1
−1
−1
1
1
1
1
−1
1
−1
−1
−1
1
−1
−1
1
−1
−1
−1
1
−1
1
1
1
1
−1
−1
1
0
1
31
1
1
−1
1
1
−1
1
1
1
1
−1
−1
−1
1
−1
1
−1
1
1
1
−1
−1
−1
−1
1
−1
−1
1
−1
−1
33
1
1
0
1
−1
0
−1
1
0
−1
0
0
−1
−1
0
1
1
0
−1
−1
0
0
−1
0
1
−1
0
−1
1
0
35
1
−1
1
1
0
−1
0
−1
1
0
1
1
1
0
0
1
1
−1
−1
0
0
−1
−1
−1
0
−1
1
0
1
0
37
1
−1
1
1
−1
−1
1
−1
1
1
1
1
−1
−1
−1
1
−1
−1
−1
−1
1
−1
−1
−1
1
1
1
1
−1
1
39
1
1
0
1
1
0
−1
1
0
1
1
0
0
−1
0
1
−1
0
−1
1
0
1
−1
0
1
0
0
−1
−1
0
41
1
1
−1
1
1
−1
−1
1
1
1
−1
−1
−1
−1
−1
1
−1
1
−1
1
1
−1
1
−1
1
−1
−1
−1
−1
−1
43
1
−1
−1
1
−1
1
−1
−1
1
1
1
−1
1
1
1
1
1
−1
−1
−1
1
−1
1
1
1
−1
−1
−1
−1
−1
45
1
−1
0
1
0
0
−1
−1
0
0
1
0
−1
1
0
1
−1
0
1
0
0
−1
−1
0
0
1
0
−1
1
0
47
1
1
1
1
−1
1
1
1
1
−1
−1
1
−1
1
−1
1
1
1
−1
−1
1
−1
−1
1
1
−1
1
1
−1
−1
49
1
1
1
1
1
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
0
1
1
51
1
−1
0
1
1
0
−1
−1
0
−1
1
0
1
1
0
1
0
0
1
1
0
−1
1
0
1
−1
0
−1
1
0
53
1
−1
−1
1
−1
1
1
−1
1
1
1
−1
1
−1
1
1
1
−1
−1
−1
−1
−1
−1
1
1
−1
−1
1
1
−1
55
1
1
−1
1
0
−1
1
1
1
0
0
−1
1
1
0
1
1
1
−1
0
−1
0
−1
−1
0
1
−1
1
−1
0
57
1
1
0
1
−1
0
1
1
0
−1
−1
0
−1
1
0
1
−1
0
0
−1
0
−1
−1
0
1
−1
0
1
1
0
59
1
−1
1
1
1
−1
1
−1
1
−1
−1
1
−1
−1
1
1
1
−1
1
1
1
1
−1
−1
1
1
1
1
1
−1
^ It is an extension of the Legendre symbol , which is only defined for positive odd prime values of
m
,
{\displaystyle m,}
Kronecker symbol , which is defined for all nonzero values of
m
.
{\displaystyle m.}
^ positive, but not necessarily distinct
^ Practically all textbooks on elementary number theory cover this material, e.g. Cohen, Hardy & Wright, Ireland and Rosen, Lemmermeyer.
^ Note that
(
2
7
)
=
(
2
15
)
=
(
2
23
)
=
1
{\displaystyle \left({\tfrac {2}{7}}\right)=\left({\tfrac {2}{15}}\right)=\left({\tfrac {2}{23}}\right)=1}
^ Typical ranges are
{
0
,
1
,
2
,
.
.
.
b
−
1
}
{\displaystyle \{0,1,2,...b-1\}}
{
0
,
±
1
,
±
2
⋯
±
b
2
}
{\displaystyle \{0,\pm 1,\pm 2\dots \pm {\tfrac {b}{2}}\}}
^ Consecutive Fibonacci numbers are used in Lames's proof as they provide an upper bound
^ Cohen
^ Riesel p. 285 (Pascal), Cohen
^ Cohen p 26 gives efficient ways to code the tests mod 2, 4, and 8: e.g. if (a%4 == 3 && m%4 == 3) is the same as if (a & m & 2).
^ If the top or the bottom argument is held fixed and the other one is allowed to vary it is a real Dirichlet character
^ See below computing JS
^ For example a primitive root must be a nonresidue, so its Jacobi symbol will be -1
^ Lucas–Lehmer does arithmetic modulo the number being tested (the largest prime so far found current record holder has over eighty million bits ) and often has to run for weeks at a time
^ Riesel p. 194ff
^ Jacobi, C. G. J. (1837). "Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie". Bericht Ak. Wiss. Berlin : 127–136. ^ Disquisitiones Arithmeticae arts 131-133^ (cases 9-14)
^ He proves e.g. that if the prime
p
{\displaystyle p}
m
{\displaystyle m}
≡
1
(
mod
4
)
{\displaystyle \equiv 1{\pmod {4}}}
m
{\displaystyle m}
p
.
{\displaystyle p.}
(
p
m
)
=
(
m
p
)
{\displaystyle \left({\frac {p}{m}}\right)=\left({\frac {m}{p}}\right)}
p
{\displaystyle p}
m
{\displaystyle m}
(
p
m
)
=
1
{\displaystyle \left({\frac {p}{m}}\right)=1}
![{\displaystyle [{\tfrac {a}{b}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/470bf662f4ea25950eaba8cd16fdf1afa210dd2c)
![{\displaystyle [{\tfrac {13}{21}}]=[{\tfrac {8}{13}}]=[{\tfrac {5}{8}}]=[{\tfrac {3}{5}}]=[{\tfrac {2}{3}}]=[{\tfrac {1}{2}}]=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9bb65bd6bfc52374818691a2f46d1805aefd3bb4)
