Symbol Jacobiego – uogólnienie symbolu Legendre’a na liczby nieparzyste niekoniecznie pierwsze: jeśli rozkład
na czynniki pierwsze to
to symbol Jacobiego jest równy przez symbol Legendre’a:
![{\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{c_{1}}\left({\frac {a}{p_{2}}}\right)^{c_{2}}\cdots \left({\frac {a}{p_{k}}}\right)^{c_{k}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12187c84d6ac1835a4a582e25669fc225e4be709)
Można zauważyć, że jeśli
jest pierwsze, symbol Jacobiego jest równy symbolowi Legendre’a.
Własności:
- Jeśli
to ![{\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7648f6b5b6a0bf2c8509bdbec4088f003203a0fd)
wtedy i tylko wtedy, gdy
i
nie są względnie pierwsze ![{\displaystyle \left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/721afb4c38cacb89beefb8481e46632d94541e9e)
![{\displaystyle \left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/022f58309eff931b56de389c59ef0e270ad89486)
![{\displaystyle \left({\frac {1}{n}}\right)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07b2a3eef03e7519a37bc536daf9abd9e5dd86a5)
jeśli ![{\displaystyle n=1\mod 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd7b6f072b667f589c8a5c9bdda8d91313b178c)
jeśli ![{\displaystyle n=3\mod 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/095d5a7118ca97c4f67d79713d99c3f9e2433d65)
jeśli
lub ![{\displaystyle n=7\mod 8}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d83630d82a96fb7ae2648c3550ab8f156302db73)
jeśli
lub ![{\displaystyle n=5\mod 8}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eef3eff5a4d89aadfe67223ab8f402b360311301)
Zachodzi też odpowiednio uogólnione prawo wzajemności reszt kwadratowych:
![{\displaystyle \left({\frac {m}{n}}\right)=\left({\frac {n}{m}}\right)(-1)^{\frac {(m-1)(n-1)}{4}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/655817b47cc6fd4dcd162df9a64b2d13084aa835)
Choć w definicji symbolu Jacobiego występuje faktoryzacja, istnieje jednak szybki algorytm obliczania go bez użycia faktoryzacji. Zauważmy, że (
nieparzyste):
![{\displaystyle \left({\frac {2^{x}y}{n}}\right)=\left({\frac {2^{x}}{n}}\right)\left({\frac {y}{n}}\right)=\left({\frac {2}{n}}\right)^{x}\left({\frac {n}{y}}\right)(-1)^{(n-1)(y-1)/4}=\left({\frac {2}{n}}\right)^{x}\left({\frac {n{\bmod {y}}}{y}}\right)(-1)^{(n-1)(y-1)/4}=\left({\frac {n{\bmod {y}}}{y}}\right)(-1)^{(n-1)(x(n+1)+2(y-1))/8}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15fe31467de26563687e290b33419dd8cb795211)
Na podstawie tego wzoru można zbudować rekurencyjny algorytm (wszystkie dzielenia i reszty modulo z wyjątkiem
to w rzeczywistości proste operacje bitowe):
Symbol-Jacobiego(a,n)
if even(n)
throw Błąd
if a == 0
return 0
if a == 1
return 1
x = 0
y = a
while even(y)
y = y / 2
x = x + 1
if odd(x) and (n mod 8 == 3 or n mod 8 == 5)
wynik = -1
else
wynik = 1
if n mod 4 == 3 and y mod 4 == 3
wynik = -wynik
if y == 1
return wynik
else
return wynik * Symbol-Jacobiego(n mod y, y)
Linki zewnętrzne
- Obliczanie symbolu Jacobiego. math.fau.edu. [zarchiwizowane z tego adresu (2008-07-20)].
- Eric W.E.W. Weisstein Eric W.E.W., Jacobi Symbol, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12] (ang.).
Jacobi symbol (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-02-02].