Symbol Jacobiego

Symbol Jacobiego – uogólnienie symbolu Legendre’a na liczby nieparzyste niekoniecznie pierwsze: jeśli rozkład $n$ na czynniki pierwsze to $p_{1}^{c_{1}}p_{2}^{c_{2}}\cdots p_{k}^{c_{k}},$ to symbol Jacobiego jest równy przez symbol Legendre’a:

\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}}

Można zauważyć, że jeśli $n$ jest pierwsze, symbol Jacobiego jest równy symbolowi Legendre’a.

Własności:

Jeśli

a=b\mod n,

to

\left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)

\left({\frac {a}{n}}\right)=0

wtedy i tylko wtedy, gdy

a

i

n

nie są względnie pierwsze

\left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right)

\left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right)

\left({\frac {1}{n}}\right)=1

\left({\frac {-1}{n}}\right)=1

jeśli

n=1\mod 4

\left({\frac {-1}{n}}\right)=-1

jeśli

n=3\mod 4

\left({\frac {2}{n}}\right)=1

jeśli

n=1\mod 8

lub

n=7\mod 8

\left({\frac {2}{n}}\right)=-1

jeśli

n=3\mod 8

lub

n=5\mod 8

Zachodzi też odpowiednio uogólnione prawo wzajemności reszt kwadratowych:

\left({\frac {m}{n}}\right)=\left({\frac {n}{m}}\right)(-1)^{\frac {(m-1)(n-1)}{4}}

Choć w definicji symbolu Jacobiego występuje faktoryzacja, istnieje jednak szybki algorytm obliczania go bez użycia faktoryzacji. Zauważmy, że ( $y$ nieparzyste):

\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}

Na podstawie tego wzoru można zbudować rekurencyjny algorytm (wszystkie dzielenia i reszty modulo z wyjątkiem $n{\bmod {y}}$ 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].

Fahrer / Team für die Suche eingeben:

Fahrer / Team für die Suche eingeben:

Eisspeedway

Symbol Jacobiego

Linki zewnętrzne