Sum of quadratic residues
What is the remainder obtained after the sum of all the quadratic residues of any prime p ( p > 3 ) is divided by p itself?
The answer is 0.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
You can use the fact that any prime has to be of the form 6k+or -1.........great solution and great job though...@Adarsh Kumar
You have to be a little careful here; you've actually counted each quadratic residue twice in your breakdown. There are only 2 p − 1 residues, not p − 1 . Since p is odd, the conclusion should still be workable, but it requires a bit of thought.
The simple solution is that the quadratic residues modulo odd prime p are the elements of the set { a k } k = 1 k = ( p − 1 ) / 2 where a k = k 2 m o d p , so using the sum of squares formula and basic modular arithmetic, we can write,
S = k = 1 ∑ ( p − 1 ) / 2 ( k 2 m o d p ) ≡ ( k = 1 ∑ ( p − 1 ) / 2 k 2 ) ≡ 6 1 ( 2 p − 1 ) ( 2 p + 1 ) ( p ) ≡ p 2 4 ( p − 1 ) ( p + 1 ) ( m o d p )
Now, p − 1 , p , p + 1 being three consecutive integers, their product is divisible by 3 . Since 3 ∣ p as p > 3 is prime, it follows that 3 ∣ ( p − 1 ) ( p + 1 ) . Also, since p > 3 is odd, both p − 1 and p + 1 are even and one of them is divisible by 4 (since they are two consecutive even integers), so the product ( p − 1 ) ( p + 1 ) is divisible by 2 × 4 = 8 .
Therefore ( p − 1 ) ( p + 1 ) is divisible by 2 4 , therefore 2 4 ( p − 1 ) ( p + 1 ) ∈ Z . Call this integer k .
Then,
S ≡ p k ≡ 0 ( m o d p )
Log in to reply
This is the actual solution in this case. Can you include this as a different solution? It is going to help a person that is looking for the right solution here. Nice job!
Log in to reply
Extremely sorry for the VERY late reply, though I wonder if it would be any use to post it as a solution now after such a long time; plus I'm not very fond of the extreme reformatting of the site, kinda puts me off somehow. If you think it's still any use to post it as a solution now, let me know!
what is 3^p?
Log in to reply
This is a very late reply since I have been inactive here for a long time, but to answer your question, it's probably a MathJax rendering problem on this site. The LaTeX code was
\not\mid
for the "not" to appear over the "mid" (divisibility symbol). It's basically saying "
3
does not divide
p
".
Very easy to understand, even for someone who barely knows anything about quadratic residues, great job!
2 1 x = 1 ∑ x = p − 1 x 2 ≡ 1 2 ( p − 1 ) ⋅ p ⋅ ( 2 p − 1 ) ( m o d p ) Since p > 3 ⟹ ( p , 1 2 ) = 1 , we can write the sum as ( p − 1 ) ⋅ p ⋅ ( 2 p − 1 ) ⋅ 1 2 − 1 ≡ 0 (mod p) . Note: Edited fixing an error mentioned in the comments
Consider p = 5 . The non-zero quadratic residues modulo p = 5 are 1 , 4 , so the sum of the quadratic residues for the case of p = 5 is 1 + 4 = 5 but your formula gives 1 2 4 × 5 × 9 = 1 5 = 5 .
Do you see the error in your solution?
Log in to reply
Perhaps it was confusing the way I framed it earlier. 15 is equal to 5 (modulo 5)
The sum of quadratic residues can be seen as the remainder as half of the remainder of 1^2 + 2^2+3^2....p^2 . Clearly, as p>3 , this is a multiple of p.
( p − 1 ) 2 ≡ 1 2 ( m o d p ) ( p − 2 ) 2 ≡ 2 2 ( m o d p ) ( p − 3 ) 2 ≡ 3 2 ( m o d p ) . . . . ( p − ( p − 2 ) ) 2 ≡ ( p − 2 ) 2 ( m o d p ) p − ( p − 1 ) ) 2 ≡ ( p − 1 ) 2 ( m o d p ) . Thus,sum of the quadratic residues = 1 2 + 2 2 + 3 2 + . . . . . + ( p − 2 ) 2 + ( p − 1 ) 2 which is the sum of the first ( p − 1 ) squares.Now,we have a formula for that.Substituting in that formula gives 6 ( p − 1 ) ( p ) ( 2 p − 1 ) . Now, when this is divided by p we are left with 6 ( p − 1 ) ( 2 p − 1 ) . Now, as long as that is an integer the remainder is 0 . Now,we have to do one more thing and that is to prove that ( p − 1 ) ( 2 p − 1 ) ≡ 0 ( m o d 6 ) . We will prove this by taking cases C a s e 1 : p ≡ 1 ( m o d 6 ) This case satisfies the condition. C a s e 2 : p ≡ 2 ( m o d 3 ) but this can't happen as p is a prime. C a s e 3 : p ≡ 3 ( m o d 6 ) This also can't happen due to the reason stated above. C a s e 4 : p ≡ 4 ( m o d 3 ) This also can't happen due to the reason stated above. C a s e 5 : p ≡ 5 ( m o d 6 ) This satisfies the condition stated.Hence proved.