• Support PF! Buy your school textbooks, materials and every day products Here!

How many values of k can be determined, such that

  • #1

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.
Screen Shot 2015-04-03 at 10.29.53 PM.png

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?
 

Answers and Replies

  • #2
18,178
7,768
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
RUber
Homework Helper
1,687
344
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
 

Related Threads on How many values of k can be determined, such that

  • Last Post
Replies
14
Views
4K
Replies
24
Views
2K
Replies
3
Views
1K
Replies
10
Views
2K
  • Last Post
Replies
3
Views
850
Replies
3
Views
2K
Replies
5
Views
662
Replies
14
Views
1K
Top