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

Tags:
1. Apr 3, 2015

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.

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. Apr 9, 2015

### Greg Bernhardt

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?

3. Apr 9, 2015

### RUber

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