History, Conventions, and Elementary Facts
Fermat, Euler, Lagrange, Legendre, and other number theorists of the 17th and 18th centuries proved some theorems and made some conjectures about quadratic residues, but the first systematic treatment is § IV of Gauss's Disquisitiones Arithmeticae (1801). Article 95 introduces the terminology "quadratic residue" and "quadratic nonresidue", and states that, if the context makes it clear, the adjective "quadratic" may be dropped.
For a given n a list of the quadratic residues modulo n may be obtained by simply squaring the numbers 0, 1, …, n − 1. Because a2 ≡ (n − a)2 (mod n), the list of squares modulo n is symmetrical around n/2, and the list only needs to go that high. This can be seen in the table at the end of the article.
Thus, the number of quadratic residues modulo n cannot exceed n/2 + 1 (n even) or (n + 1)/2 (n odd).
The product of two residues is always a residue.
Read more about this topic: Quadratic Residue
Famous quotes containing the words elementary and/or facts:
“If men as individuals surrender to the call of their elementary instincts, avoiding pain and seeking satisfaction only for their own selves, the result for them all taken together must be a state of insecurity, of fear, and of promiscuous misery.”
—Albert Einstein (1879–1955)
“Conventionalities are at length as bad as impurities. Even the facts of science may dust the mind by their dryness, unless they are in a sense effaced each morning, or rather rendered fertile by the dews of fresh and living truth.”
—Henry David Thoreau (1817–1862)