Матеріал з Вікіпедії — вільної енциклопедії.
Символ Якобі — в теорії чисел узагальнення символу Лежандра для довільних додатних непарних цілих чисел:
- якщо розклад
на прості множники має вигляд
, то символ Якобі рівний:
![{\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)
де в правій частині є звичайні символи Лежандра.
Якщо
є простим числом то символ Якобі дорівнює символу Лежандра.
Введена в 1837 році Карлом Якобі.
Властивості
- Якщо
, то ![{\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7648f6b5b6a0bf2c8509bdbec4088f003203a0fd)
тоді і тільки тоді, коли
і
не є взаємно простими
![{\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)
якщо ![{\displaystyle n=1\mod 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd7b6f072b667f589c8a5c9bdda8d91313b178c)
якщо ![{\displaystyle n=3\mod 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/095d5a7118ca97c4f67d79713d99c3f9e2433d65)
якщо
або ![{\displaystyle n=7\mod 8}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d83630d82a96fb7ae2648c3550ab8f156302db73)
якщо
або ![{\displaystyle n=5\mod 8}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eef3eff5a4d89aadfe67223ab8f402b360311301)
Узагальнений квадратичний закон взаємності:
![{\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)
Приклад обчислень
![{\displaystyle \left({\frac {1001}{9907}}\right)=\left({\frac {9907}{1001}}\right)=\left({\frac {898}{1001}}\right)=\left({\frac {2}{1001}}\right)\left({\frac {449}{1001}}\right)=\left({\frac {449}{1001}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8842a2cbbdc41228a3a7921307a056a8fb1f0884)
![{\displaystyle =\left({\frac {1001}{449}}\right)=\left({\frac {103}{449}}\right)=\left({\frac {449}{103}}\right)=\left({\frac {37}{103}}\right)=\left({\frac {103}{37}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a41a7e69128a9fb9521327d7c084b0b8b2f10d63)
![{\displaystyle =\left({\frac {29}{37}}\right)=\left({\frac {37}{29}}\right)=\left({\frac {8}{29}}\right)=\left({\frac {4}{29}}\right)\left({\frac {2}{29}}\right)=-1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55964f682eb186855a0a52498eefb9a7cf314fbf)
Алгоритм
ЯКОБІ(a, n)[1]:73
Вхід: непарне ціле число
і ціле
Вихід: символ Якобі
(відповідно символ Лежандра, якщо
просте).
- Якщо
тоді повернути(0).
- Якщо
тоді повернути(1).
- Записати
де
непарне.
- Якщо
парне, тоді покласти
Інакше, покласти
якщо
або покласти
якщо ![{\displaystyle n\equiv \pm 3{\pmod {8}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/477fbdd5ea53544da51ef98a2106411c71e2a564)
- Якщо
і
тоді покласти ![{\displaystyle s\gets -s.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5803fd881d6b2464dc5d68784e53eff0eecd13c5)
- Покласти
![{\displaystyle n_{1}\gets n\mod a_{1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a06265fda3b3dd6dd597ec309fa86c333848dc3)
- Якщо
тоді повернути(s); інакше повернути(
ЯКОБІ
).
Примітки
Література