# How many values of k can be determined, such that

## Homework Statement

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.

## Homework Equations

On image. ## 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?

Related Precalculus Mathematics Homework Help News on Phys.org
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?

RUber
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, (8)

if 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