[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Jacobi symbol problem

Posted on 2009-04-26
4
Medium Priority
?
270 Views
Last Modified: 2012-06-21
n is odd and square-free
The sum (k/n)=0, where the sum taken over all k in a reduced set of residues modulo n. Use this to show that the number of integers in a reduced set of residues modulo n such that (k/n)=1 is equal to the number with (k/n)= -1.
0
Comment
Question by:AlephNought
  • 2
2 Comments
 

Author Comment

by:AlephNought
ID: 24241161
I'm not looking for an answer at all. I'd just like to understand how to approach the problem. For example, I have already determined that the sum is 0. (This wasn't part of the question, so I entered it in b/c I thought this fact might be useful somehow.) I think this question is sayin that the number of quadratic residues (k/n)=(k/p1)(k/p2)...(k/pr) and quadratic nonresidues are equaivatent, but isn't that why the sum is 0? So I really don't know what more the question wants me to show.
0
 

Accepted Solution

by:
AlephNought earned 0 total points
ID: 24247079
sum(k/n)= sum(ak/n)= sum (a/n)(k/n)
There exists some a such that (a/n)=-1
=> sum(k/n)= -sum(k/n)=0
Moreover, since the only choices for (k/n) are plus and minus one and the sum equals 0, there must necessarily be an equal amount of (k/n)=1 and (k/n)= -1
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
This article provides a brief introduction to tissue engineering, the process by which organs can be grown artificially. It covers the problems with organ transplants, the tissue engineering process, and the current successes and problems of the tec…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Suggested Courses

834 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question