Let n be a positive integer. (a) Prove the following statement: For all integers
ID: 3145858 • Letter: L
Question
Let n be a positive integer.
(a) Prove the following statement: For all integers x, (n-x)^2 = x^2 mod n.
(b) We say an integer r is a quadratic residue modulo n if 0<=r<n and there exists an integer x such that x^2= r mod n. Using part (a) or otherwise, show that the number of quadratic residues modulo n is at most (2n+1)/2 if n is odd and at most n/2+1 if n is even.
(c) Give a proof or a counterexample for the following statement: For every positive integer n, the number of quadratic residues modulo n is equal to (2n+1)/2 if n is odd and is equal to n/2 +1 if n is even.
Explanation / Answer
(a) (n-x)2 = n2 - 2xn + x2
= n(n - 2x) + x2
Thus (n-x)2 leaves remainder x2 when divided by n
=> (n-x)2 = x2 mod n.
(b) From part (a), (n-x)2 = x2 mod n.
If x2 = r mod n
=> (n-x)2 = r mod n.
Thus every r is a quadratic residue of two different integers.
There are atmost n + 1 remainders.
If n is even, n-x = x if x = n/2.
Thus the number of remainders <= n/2 + 1.
If n is odd, number of remainders <= n <= (2n+1)/2.
(c) Counterexample: n = 4
The quadratic residues are 1 as 22 = 0 mod 4
1 as 12 = 1 mod 4
Thus there are 2 quadratic residues for 4.
But n/2 + 1 = 4/2 + 1 = 3.
Thus the statement is not true.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.