The Legendre symbol is a shorthand notation used in number theory , a branch of mathematics . It is named after the French mathematician Adrien-Marie Legendre .
Definition and notation
The Legendre symbol indicates whether the number is a quadratic remainder modulo or a quadratic non- remainder modulo . It must be an integer and a prime number .
a
{\ displaystyle a}
p
{\ displaystyle p}
p
{\ displaystyle p}
a
{\ displaystyle a}
p
{\ displaystyle p}
The following applies:
(
a
p
)
=
{
1
if
a
quadratic remainder modulo
p
is
-
1
if
a
quadratic non-remainder modulo
p
is
0
if
a
a multiple of
p
is
{\ displaystyle \ left ({\ frac {a} {p}} \ right) = {\ begin {cases} 1 & {\ mbox {if}} a {\ mbox {quadratic remainder modulo}} p {\ mbox {is }} \\ - 1 & {\ mbox {if}} a {\ mbox {quadratic non-remainder modulo}} p {\ mbox {is}} \\ 0 & {\ mbox {if}} a {\ mbox {a multiple of} } p {\ mbox {ist}} \ end {cases}}}
The Legendre symbol is a special case of the Jacobi symbol that has the same spelling. Further notation variants for the Legendre symbol are and .
(
a
/
p
)
{\ displaystyle (a / p)}
L.
(
a
,
p
)
{\ displaystyle L (a, p)}
calculation
The Euler's criterion indicates how the Legendre symbol for itself odd prime number calculate can:
p
{\ displaystyle p}
(
a
p
)
≡
a
p
-
1
2
(
mod
p
)
{\ displaystyle \ left ({\ frac {a} {p}} \ right) \ equiv a ^ {\ frac {p-1} {2}} {\ pmod {p}}}
.
The following applies to the only even prime number :
2
{\ displaystyle 2}
-
1
≡
1
(
mod
2
)
{\ displaystyle -1 \ equiv 1 {\ pmod {2}}}
.
Every odd number is a quadratic remainder and every even number is a multiple of 2, so modulo 2 there are no non-residues:
(
a
2
)
=
a
mod
2
{\ displaystyle \ left ({\ frac {a} {2}} \ right) = a {\ bmod {2}}}
.
Zolotareff's lemma provides another calculation option , according to that for odd prime numbers
(
a
p
)
=
so-called
(
π
a
,
p
)
{\ displaystyle \ left ({\ frac {a} {p}} \ right) = \ operatorname {sgn} (\ pi _ {a, p})}
applies, where that through
π
a
,
p
{\ displaystyle \ pi _ {a, p}}
π
a
,
p
(
k
)
≡
a
⋅
k
(
mod
p
)
{\ displaystyle \ pi _ {a, p} (k) \ equiv a \ cdot k {\ pmod {p}}}
defined permutation of the numbers of , and denotes the sign of a permutation.
k
=
0
,
...
p
-
1
{\ displaystyle k = 0, \ dotsc p-1}
so-called
{\ displaystyle \ operatorname {sgn}}
Examples
2 is a quadratic remainder modulo 7 - in fact, yes :
2
≡
3
2
(
mod
7th
)
{\ displaystyle 2 \ equiv 3 ^ {2} {\ pmod {7}}}
(
2
7th
)
≡
2
7th
-
1
2
=
2
3
≡
1
mod
7th
{\ displaystyle \ left ({\ frac {2} {7}} \ right) \ equiv 2 ^ {\ frac {7-1} {2}} = 2 ^ {3} \ equiv 1 \ mod 7}
5 is a quadratic non-remainder modulo 7:
(
5
7th
)
≡
5
7th
-
1
2
=
5
3
≡
6th
≡
-
1
mod
7th
{\ displaystyle \ left ({\ frac {5} {7}} \ right) \ equiv 5 ^ {\ frac {7-1} {2}} = 5 ^ {3} \ equiv 6 \ equiv -1 \ mod 7}
14 is divisible by 7 (i.e. neither remainder nor non-remainder of 7):
(
14th
7th
)
≡
14th
7th
-
1
2
=
14th
3
≡
0
mod
7th
{\ displaystyle \ left ({\ frac {14} {7}} \ right) \ equiv 14 ^ {\ frac {7-1} {2}} = 14 ^ {3} \ equiv 0 \ mod 7}
Calculation rules
The quadratic reciprocity law makes important statements about calculating with the Legendre symbol.
In addition, apply to all whole numbers , all prime numbers and the following calculation rules:
a
{\ displaystyle a}
b
{\ displaystyle b}
p
{\ displaystyle p}
a
≡
b
(
mod
p
)
⇒
(
a
p
)
=
(
b
p
)
{\ displaystyle a \ equiv b {\ pmod {p}} \ Rightarrow \ left ({\ frac {a} {p}} \ right) = \ left ({\ frac {b} {p}} \ right)}
(
a
p
)
⋅
(
b
p
)
=
(
a
⋅
b
p
)
{\ displaystyle \ left ({\ frac {a} {p}} \ right) \ cdot \ left ({\ frac {b} {p}} \ right) = \ left ({\ frac {a \ cdot b} {p}} \ right)}
∑
k
=
1
p
-
1
(
k
p
)
=
0
{\ displaystyle \ sum _ {k = 1} ^ {p-1} \ left ({\ frac {k} {p}} \ right) = 0}
for .
p
≠
2
{\ displaystyle p \ neq 2}
Special values
The following applies to
all odd prime numbers
p
{\ displaystyle p}
(
1
p
)
=
1
{\ displaystyle \ left ({\ frac {1} {p}} \ right) = 1}
(
2
p
)
=
(
-
1
)
p
2
-
1
8th
=
{
1
For
p
≡
1
or
7th
(
mod
8th
)
-
1
For
p
≡
3
or
5
(
mod
8th
)
.
{\ displaystyle \ left ({\ frac {2} {p}} \ right) = (- 1) ^ {\ frac {p ^ {2} -1} {8}} = {\ begin {cases} 1 & { \ mbox {for}} p \ equiv 1 {\ mbox {or}} 7 {\ pmod {8}} \\ - 1 & {\ mbox {for}} p \ equiv 3 {\ mbox {or}} 5 {\ pmod {8}}. \ end {cases}}}
(
-
1
p
)
=
(
-
1
)
p
-
1
2
=
{
1
For
p
≡
1
(
mod
4th
)
-
1
For
p
≡
3
(
mod
4th
)
.
{\ displaystyle \ left ({\ frac {-1} {p}} \ right) = (- 1) ^ {\ frac {p-1} {2}} = {\ begin {cases} 1 & {\ mbox { for}} p \ equiv 1 {\ pmod {4}} \\ - 1 & {\ mbox {for}} p \ equiv 3 {\ pmod {4}}. \ end {cases}}}
These special values are sufficient to calculate each non-vanishing Legendre symbol by repeatedly dividing the "numerator" into prime factors, applying the quadratic reciprocity law and modulo reduction. So is for example
(
10
31
)
=
(
2
31
)
(
5
31
)
=
1
⋅
(
-
1
)
5
-
1
2
31
-
1
2
(
31
5
)
=
(
1
5
)
=
1
{\ displaystyle \ left ({\ frac {10} {31}} \ right) = \ left ({\ frac {2} {31}} \ right) \ left ({\ frac {5} {31}} \ right) = 1 \ cdot (-1) ^ {{\ frac {5-1} {2}} {\ frac {31-1} {2}}} \ left ({\ frac {31} {5}} \ right) = \ left ({\ frac {1} {5}} \ right) = 1}
The special position of the number 3
With integer division, the number 3 returns the values 0, 1 and −1 as modulo. This corresponds exactly to the values of the Legendre symbol. The following applies:
(
a
3
)
≡
a
3
-
1
2
mod
3
=
a
mod
3
{\ displaystyle \ left ({\ frac {a} {3}} \ right) \ equiv a ^ {\ frac {3-1} {2}} \ \ operatorname {mod} \ 3 = a \ \ operatorname {mod } \ 3}
On the other hand, the following also applies:
(
3
p
)
=
∏
l
=
1
p
-
1
2
[
3
-
4th
sin
2
(
2
π
l
p
)
]
{\ displaystyle \ left ({\ frac {3} {p}} \ right) = \ prod _ {l = 1} ^ {\ frac {p-1} {2}} \ left [3-4 \, \ sin ^ {2} {\ left ({\ frac {2 \ pi l} {p}} \ right)} \ right]}
Special features of prime numbers
See under Pythagorean prime number .
<img src="https://de.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">