Матеріал з Вікіпедії — вільної енциклопедії.
Символ Якобі — в теорії чисел узагальнення символу Лежандра для довільних додатних непарних цілих чисел:
- якщо розклад на прості множники має вигляд , то символ Якобі рівний:
де в правій частині є звичайні символи Лежандра.
Якщо є простим числом то символ Якобі дорівнює символу Лежандра.
Введена в 1837 році Карлом Якобі.
Властивості
- Якщо , то
- тоді і тільки тоді, коли і не є взаємно простими
- якщо
- якщо
- якщо або
- якщо або
Узагальнений квадратичний закон взаємності:
Приклад обчислень
Алгоритм
ЯКОБІ(a, n)[1]:73
Вхід: непарне ціле число і ціле
Вихід: символ Якобі (відповідно символ Лежандра, якщо просте).
- Якщо тоді повернути(0).
- Якщо тоді повернути(1).
- Записати де непарне.
- Якщо парне, тоді покласти Інакше, покласти якщо або покласти якщо
- Якщо і тоді покласти
- Покласти
- Якщо тоді повернути(s); інакше повернути(ЯКОБІ).
Примітки
Література