All mathematicans are not white...........it is just that nowadays whitey dominates the publishing industry...............

More than 1,800 years ago the Chinese text Sun Zi Suan Jing contained a statement of what is now referred to as the Chinese Remainder Theorem. This theorem gives a very efficient algorithm that reduces the study of the solutions to a polynomial equation in arithmetic modulo a whole number m, to the study of the same equation in arithmetic modulo the factors of m of the form pa, where p is a prime number and a is a positive whole number. In fact, it turns out that the key case to consider is when m is a prime number. Thus, for the rest of this article, we will only consider arithmetic modulo a prime number p.

Recall that a prime number is a whole number greater than 1, which is only divisible by 1 and by itself. Examples are 2, 3, 5, 7, 11, 13, 17, and 19, but not for instance 15, which is divisible by 3 and 5. Every positive whole number can be written uniquely as a product of prime numbers (up to order). In some way, prime numbers are a bit like the atoms of which all other whole numbers are composed.

The first really great achievement in the study of modular arithmetic was Carl Friedrich Gauss’s proof in 1796 of his celebrated law of quadratic reciprocity, which had previously been conjectured by Leonhard Euler and Joseph Lagrange. This was supposed to have been Gauss’s favorite theorem, and he kept coming back to it during his life, giving eight different proofs. It states that

if p is a prime number, then the number of square roots of an integer n in arithmetic modulo p depends only on pmodulo 4n.

On the face of it, this may not seem surprising, but I would stress that there is no apparent reason why trying to solve the equation

X 2 ≡ n mod p

should have anything to do with p modulo 4n. Thirty years after I first learnt how to prove this theorem, it still seems miraculous to me.

Gauss’s theorem also provides a very effective way of determining the number of square roots a whole number has in arithmetic modulo a prime number p. For example, one could ask how many square roots 3 has in arithmetic modulo 20132011, which is a prime number. You could, in theory, check all the 20132011 possibilities and determine the answer, but (without a computer) this would take a very long time. On the other hand

20132011 = 1677667 × 12 + 7