Distribution of Quadratic Residues
Although quadratic residues appear to occur in a rather random pattern modulo n, and this has been exploited in such applications as acoustics and cryptography, their distribution also exhibits some striking regularities.
Using Dirichlet's theorem on primes in arithmetic progressions, the law of quadratic reciprocity, and the Chinese remainder theorem (CRT) it is easy to see that for any M > 0 there are primes p such that the numbers 1, 2, …, M are all residues modulo p.
For example, if p ≡ 1 (mod 8), (mod 12), (mod 5) and (mod 28), then by the law of quadratic reciprocity 2, 3, 5, and 7 will all be residues modulo p, and thus all numbers 1–10 will be. The CRT says that this is the same as p ≡ 1 (mod 840), and Dirichlet's theorem says there are an infinite number of primes of this form. 2521 is the smallest, and indeed 12 ≡ 1, 10462 ≡ 2, 1232 ≡ 3, 22 ≡ 4, 6432 ≡ 5, 872 ≡ 6, 6682 ≡ 7, 4292 ≡ 8, 32 ≡ 9, and 5292 ≡ 10 (mod 2521).
Read more about this topic: Quadratic Residue
Famous quotes containing the words distribution of, distribution and/or residues:
“In this distribution of functions, the scholar is the delegated intellect. In the right state, he is, Man Thinking. In the degenerate state, when the victim of society, he tends to become a mere thinker, or, still worse, the parrot of other men’s thinking.”
—Ralph Waldo Emerson (1803–1882)
“The question for the country now is how to secure a more equal distribution of property among the people. There can be no republican institutions with vast masses of property permanently in a few hands, and large masses of voters without property.... Let no man get by inheritance, or by will, more than will produce at four per cent interest an income ... of fifteen thousand dollars] per year, or an estate of five hundred thousand dollars.”
—Rutherford Birchard Hayes (1822–1893)
“You were born into a different world that will present you with different gifts and challenges. A new vision of manhood will be called for that does not tie so closely into the more aggressive and competitive residues of our male character. You will need to search out new ways of expressing strength, showing mastery, and exhibiting courage—ways that do not depend upon confronting the world before you as an adversary.”
—Kent Nerburn (20th century)