Chinese Remainder Theorem

The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra. In its basic form, the Chinese remainder theorem will determine a number n that when divided by some given divisors leaves given remainders.

For example, what is the lowest number n that when divided by 3 leaves a remainder of 2, when divided by 5 leaves a remainder of 3, and when divided by 7 leaves a remainder of 2? A common introductory example is a woman who tells a policeman that she lost her basket of eggs, and that if she took three at a time out of it, she was left with 2, if she took five at a time out of it she was left with 3, and if she took seven at a time out of it she was left with 2. She then asks the policeman what is the minimum number of eggs she must have had. The answer to both problems is 23.

Read more about Chinese Remainder Theorem:  Theorem Statement, Existence, Finding The Solution With Basic Algebra and Modular Arithmetic, A Constructive Algorithm To Find The Solution, Statement For Principal Ideal Domains, Statement For General Rings, Applications, Non-commutative Case: A Counter-example

Famous quotes containing the words remainder and/or theorem:

    Then I had only prisoners’ thoughts. I awaited the daily walk which I took in the yard, or my lawyer’s visit. I managed the remainder of my time very well. I have often thought that if I was made to live in a dry tree trunk, without any other occupation but to watch the flower of the sky above my head, I would have gradually gotten used to it.
    Albert Camus (1913–1960)

    To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.
    Albert Camus (1913–1960)