13 lines
766 B
Text
13 lines
766 B
Text
The '''[https://en.wikipedia.org/wiki/Jacobi_symbol Jacobi symbol]''' is a multiplicative function that generalizes the Legendre symbol. Specifically, the Jacobi symbol (a | n) equals the product of the Legendre symbols (a | p_i)^(k_i), where n = p_1^(k_1)*p_2^(k_2)*...*p_i^(k_i) and the Legendre symbol (a | p) denotes the value of a ^ ((p-1)/2) (mod p)
|
|
* (a | p) ≡ 1 if a is a square (mod p)
|
|
* (a | p) ≡ -1 if a is not a square (mod p)
|
|
* (a | p) ≡ 0 if a ≡ 0
|
|
|
|
If n is prime, then the Jacobi symbol (a | n) equals the Legendre symbol (a | n).
|
|
|
|
;Task:
|
|
Calculate the Jacobi symbol (a | n).
|
|
|
|
;Reference:
|
|
* [https://en.wikipedia.org/wiki/Jacobi_symbol Wikipedia article on Jacobi symbol].
|
|
|