Jacobi symbol problem

Posted on 2009-04-26
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.
Question by:AlephNought

    Author Comment

    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.

    Accepted Solution

    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

    Featured Post

    How your wiki can always stay up-to-date

    Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
    - Increase transparency
    - Onboard new hires faster
    - Access from mobile/offline

    Join & Write a Comment

    Suggested Solutions

    Title # Comments Views Activity
    Trying to solve some simple triangle Math 28 78
    Michel Meyer experiments 40 194
    Representing TIME in Excel 8 41
    Where is the math error. 13 58
    A Guide to the PMT, FV, IPMT and PPMT Functions In MS Excel we have the PMT, FV, IPMT and PPMT functions, which do a fantastic job for interest rate calculations.  But what if you don't have Excel ? This article is for programmers looking to re…
    Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
    Hi everyone! This is Experts Exchange customer support.  This quick video will show you how to change your primary email address.  If you have any questions, then please Write a Comment below!
    In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

    734 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

    Need Help in Real-Time?

    Connect with top rated Experts

    19 Experts available now in Live!

    Get 1:1 Help Now