Anonymous user
Jacobi symbol: Difference between revisions
no edit summary
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible) |
No edit summary |
||
Line 1:
{{task}}
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)
|