Re: Jacobi symbols of higher degree

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 10/14/05 

Date: Fri, 14 Oct 2005 16:40:36 +0000 (UTC)

MB wrote:
>one can generalize the Legendre symbol to an rth-power-residue symbol
>in the expected way. I.e., for p odd prime, r>=2:
>
>(x|p)_r = 1 if x is an r-th power mod p and (x,p)=1
>(x|p)_r = -1 if x is not an r-th power mod p and (x,p)=1
>(x|p)_r = 0 if (x,p)!=1.

The more usual definition is (x|p)_r = x^{(p-1)/r} (mod p).
There's a natural way to generalize to mod n, but then I don't
know how to calculate it without knowing the factorization of n.