The Jacobi symbol is a generalization of the Legendre symbol (a/n) for when n isn’t prime. Let
n=p1α 1… pkα k |
be the prime factorization of n. The Jacobi symbol of a is defined by:
⎛ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎠ | = | ⎛ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎠ |
| … | ⎛ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎠ |
|
Where the left hand side is the Jacobi symbol and the right hand side contains Legendre symbols. The jacobi_symbol command computes the Jacobi symbol.
Examples.
1 |
−1 |
0 |