61.2 The number of quadratic residues mod m

1. It is well known that if p is a prime number not equal to 2, then exactly half the non-zero residues of p are quadratic residues (that is, squares in the arithmetic mod p ). What happens if the modulus m is not prime? We can look at this problem in two ways: we can insist that our residues are relatively prime to m , or we can consider all the residues.