1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How many values of k can be determined, such that

  1. Apr 3, 2015 #1
    1. The problem statement, all variables and given/known data
    How many values of k can be determined in general, such that (k/p) = ((k+1) /p) = 1, where 1 =< k <=p-1?
    Note: (k/p) and ((k+1)/p) are legendre symbols

    Question is more clearer on the image attached.

    2. Relevant equations
    On image.
    Screen Shot 2015-04-03 at 10.29.53 PM.png
    3. The attempt at a solution
    I've tried C(7)=#{1} and it equals to 1 set or C(7) = 1 and

    C(13) = #{3, 9} = 2

    I also plugged in p = 4n+1 into C( p) which makes it equal n-1.
    As well, p = 4k+3 into C( p) makes it equal to n.

    This in fact does make the above equation of C( p) true. But how do I show that it works for all prime p that are odd?
  2. jcsd
  3. Apr 9, 2015 #2
    Thanks for the post! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?
  4. Apr 9, 2015 #3


    User Avatar
    Homework Helper

    There is a lot of stuff in here that I have never worked with.
    Perhaps you could provide a little more in the line of relevant equations or properties of the Legendre Symbols.

    e.g.: http://mathworld.wolfram.com/LegendreSymbol.html

    In general,
    NumberedEquation4.gif (8)

    if Inline21.gif is an odd prime.

    Using this, ##\left( \frac ap \right) = 1 \implies a^{(p-1)/2} \mod p = 1## and ##\left( \frac {a+1}{p} \right) = 1 \implies (a+1)^{(p-1)/2} \mod p = 1##

    I see you have already worked out the first few...and noticing a pattern, perhaps induction might work...but that is quite tricky with primes.

    For example,
    3 has quadratic residues {1} , C(3) = 0.
    5 has quadratic residues {1,4}, C(5) = 0.
    7 has quadratic residues {1,2, 4}, C(7) = 1.
    11 has quadratic residues {1, 3, 4, 5, 9}, C(11) = 2
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted