How many values of k can be determined, such that

[coolusername]

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?

 

[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