The Jacobi symbol, written (n/m) or (n/m) is defined for positive odd m as (n/m) = (n/p_1)^(a_1) (n/p_2)^(a_2) ...(n/p_k)^(a_k), where m = p_1^(a_1) p_2^(a_2) ...p_k^(a_k) is the prime factorization of m and (n/p_i) is the Legendre symbol. (The Legendre symbol is equal to ± 1 depending on whether n is a quadratic residue modulo m.) Therefore, when m is a prime, the Jacobi symbol reduces to the Legendre symbol.