From: Severian Subject: Re: Higher residuosity and reciprocity ? Date: Sat, 22 Jan 2000 11:46:23 +0000 Newsgroups: sci.math Summary: [missing] quadratic_residue@my-deja.com wrote: > > Given a modulus n, an element x, and an exponent e, when and how > can I determine if x is an e'th residue mod n? > > In the case where n is a prime, and e=2, I have Euhler's criterion > for computing the Legendre symbol. In the case where n is composite, > factorization unknown and intractable, and e=2, I can compute the Jacobi > symbol -- which does not actually tell me if x is a quadratic residue, > but is "close." Computing the Jacobi symbol efficiently without the > factors of n depends on identities which are drawn from quadratic > reciprocity. > > I know that if gcd (e, phi(n) ) = 1, then taking x^e mod n is a > permutation. So everything is an e'th residue. What happens when > gcd(e, phi(n) ) != 1 ? > > I have been playing with this a very little bit using some stupid lisp > functions. My conjecture at this point is that if gcd(e, phi(n)) != 1, > for prime modulus n, then the number of residues is phi(n)/e. Further, > it seems that I can test for an e'th residue by computing > > x^{(n-1)/e} mod n > > which is 1 if x is a residue, not 1 otherwise. This isn't even true for n = 15, e = 2. Here phi(n) = 8, but the only quadratic residues are 1 and 4. Indeed here (n-1)/e = 4, but all numbers prime to 15 satisfy x^4 = 1 (mod 15). The condition you gave is necessary but not sufficient for e-th power residuacity. > Question 1 : am I on the right track so far? > Question 2 : Is there a higher reciprocity law like quadratic > reciprocity, and can I use it to compute a "e'th > Jacobi symbol" ? > Question 3 : Do any number theory textbooks cover this at all? > I went to the library and pulled a few off the shelf, > but they only seemed to discuss quadratic reciprocity. There is a theory of higher power reciprocity, but it's more difficult than quadratic reciprocity, and it involves working with number fields containing the appropriate roots of unity. For instance 4-th power reciprocity involves working with symbols (u/v)_4 where u and v are numbers of the form a + bi where i^2 = -1. These symbols take the values, 1, -1, i or -i. This is dealt with in more advanced texts. A good one is Ireland and Rosen's "A Classical Intoduction to Modern Number Theory" published by Springer. This deals in detail with cubic and quartic reciprocity. The theory goes back to Gauss, Jacobi and Eisenstein. Severian ============================================================================== From: quadratic_residue@my-deja.com Subject: Re: Higher residuosity and reciprocity ? Date: Sat, 22 Jan 2000 19:50:36 GMT Newsgroups: sci.math In article <3889988F.DC967533@matachin.fsnet.co.uk>, Severian wrote: > > for prime modulus n, then the number of residues is phi(n)/e. Further, > > it seems that I can test for an e'th residue by computing > > > > x^{(n-1)/e} mod n > > > > which is 1 if x is a residue, not 1 otherwise. > > This isn't even true for n = 15, e = 2. Here phi(n) = 8, but the only > quadratic residues are 1 and 4. Indeed here (n-1)/e = 4, but all numbers > prime to 15 satisfy x^4 = 1 (mod 15). The condition you gave is > necessary > but not sufficient for e-th power residuacity. > I'm sorry - I should have been more clear. I was only making the conjecture for a prime n. I used n instead of p as notation because my statement of the question was for arbitrary n. 15 isn't prime, so it doesn't surprise me that the conjecture fails. The example is much appreciated in terms of thinking about n = pq, p and q prime, though. > This is dealt with in more advanced texts. A good one is Ireland and > Rosen's "A Classical Intoduction to Modern Number Theory" published > by Springer. This deals in detail with cubic and quartic reciprocity. > The theory goes back to Gauss, Jacobi and Eisenstein. Thanks for the references! Thanks much, -David Molnar Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: Kurt Foster Subject: Re: Higher residuosity and reciprocity ? Date: Sat, 22 Jan 2000 15:40:17 GMT Newsgroups: sci.math In <86b1pa$vsc$1@nnrp1.deja.com>, quadratic_residue@my-deja.com said: . Given a modulus n, an element x, and an exponent e, when and how . can I determine if x is an e'th residue mod n? You might want to consult a littlle book in the "LECTURES IN ADVANCED MATHEMATICS" series, "Cyclotomy and Difference Sets" by Thomas Storer. Library of Congress Catalog number 67-24525 . There are also any number of books (look, e.g. for the authors Ireland and Rosen) on character sums and various reciprocity laws. Books on algebraic number theory and classfield theory will probably cover Artin's reciprocity law. You might want to look at the URL http://www.wolfram.com/Q/QuadraticRecipricityTheorem.html It seems that a generalized reciprocity law, the local Langlands correspondence, conjectured by Langlands around 1970, has recently been proved by Michael Harris of the University of Paris VII and Richard Taylor of Harvard. The above URL has some material on Langlands's work. See also "The nonabelian reciprocity law for local fields" by Jonathan Rogawski (UCLA), in the January 2000 "Notices of the American Mathematical Society".