Chinese remainder theorem

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime (no two divisors share a common factor other than 1).

For example, if we know that the remainder of n divided by 3 is 2, the remainder of n divided by 5 is 3, and the remainder of n divided by 7 is 2, then without knowing the value of n, we can determine that the remainder of n divided by 105 (the product of 3, 5, and 7) is 23. Importantly, this tells us that if n is a natural number less than 105, then 23 is the only possible value of n.

The earliest known statement of the theorem is by the Chinese mathematician Sunzi in the Sunzi Suanjing in the 3rd to 5th century CE.

The Chinese remainder theorem is widely used for computing with large integers, as it allows replacing a computation for which one knows a bound on the size of the result by several similar computations on small integers.

The Chinese remainder theorem (expressed in terms of congruences) is true over every principal ideal domain. It has been generalized to any ring, with a formulation involving two-sided ideals.

Over principal ideal domains[edit]

In § Statement, the Chinese remainder theorem has been stated in three different ways: in terms of remainders, of congruences, and of a ring isomorphism. The statement in terms of remainders does not apply, in general, to principal ideal domains, as remainders are not defined in such rings. However, the two other versions make sense over a principal ideal domain $R$ : it suffices to replace "integer" by "element of the domain" and $\mathbb {Z}$ by $R$ . These two versions of the theorem are true in this context, because the proofs (except for the first existence proof), are based on Euclid's lemma and Bézout's identity, which are true over every principal domain.

However, in general, the theorem is only an existence theorem and does not provide any way for computing the solution, unless one has an algorithm for computing the coefficients of Bézout's identity.

Applications[edit]

Sequence numbering[edit]

The Chinese remainder theorem has been used to construct a Gödel numbering for sequences, which is involved in the proof of Gödel's incompleteness theorems.

Fast Fourier transform[edit]

The prime-factor FFT algorithm (also called Good-Thomas algorithm) uses the Chinese remainder theorem for reducing the computation of a fast Fourier transform of size $n_{1}n_{2}$ to the computation of two fast Fourier transforms of smaller sizes $n_{1}$ and $n_{2}$ (providing that $n_{1}$ and $n_{2}$ are coprime).

Encryption[edit]

Most implementations of RSA use the Chinese remainder theorem during signing of HTTPS certificates and during decryption.

The Chinese remainder theorem can also be used in secret sharing, which consists of distributing a set of shares among a group of people who, all together (but no one alone), can recover a certain secret from the given set of shares. Each of the shares is represented in a congruence, and the solution of the system of congruences using the Chinese remainder theorem is the secret to be recovered. Secret sharing using the Chinese remainder theorem uses, along with the Chinese remainder theorem, special sequences of integers that guarantee the impossibility of recovering the secret from a set of shares with less than a certain cardinality.

Covering system

Hasse principle

Residue number system

Dauben, Joseph W. (2007), "Chapter 3: Chinese Mathematics", in Katz, Victor J. (ed.), The Mathematics of Egypt, Mesopotamia, China, India and Islam : A Sourcebook, Princeton University Press, pp. 187–384, 978-0-691-11485-9

ISBN

Dence, Joseph B.; Dence, Thomas P. (1999), , Academic Press, ISBN 9780122091308

Elements of the Theory of Numbers

Duchet, Pierre (1995), "Hypergraphs", in Graham, R. L.; ; Lovász, L. (eds.), Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, pp. 381–432, MR 1373663. See in particular Section 2.5, "Helly Property", pp. 393–394.

Grötschel, M.

Gauss, Carl Friedrich (1986), , translated by Clarke, Arthur A. (Second, corrected ed.), New York: Springer, ISBN 978-0-387-96254-2

Disquisitiones Arithemeticae

Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (2nd ed.), Springer-Verlag, 0-387-97329-X

ISBN

(1986), "Computational aspects of the Aryabhata algorithm" (PDF), Indian Journal of History of Science, 21 (1): 62–71

Kak, Subhash

Katz, Victor J. (1998), (2nd ed.), Addison Wesley Longman, ISBN 978-0-321-01618-8

A History of Mathematics / An Introduction

Libbrecht, Ulrich (1973), Chinese Mathematics in the Thirteenth Century: the "Shu-shu Chiu-chang" of Ch'in Chiu-shao, Dover Publications Inc, 978-0-486-44619-6

ISBN

(1952), "The general Chinese remainder theorem", The American Mathematical Monthly, 59: 365–370, doi:10.2307/2306804, MR 0048481

Ore, Øystein

Ore, Oystein (1988) [1948], , Dover, ISBN 978-0-486-65620-5

Number Theory and Its History

(2002), Fibonacci's Liber Abaci, translated by Sigler, Laurence E., Springer-Verlag, pp. 402–403, ISBN 0-387-95419-8

Pisano, Leonardo

Rosen, Kenneth H. (1993), Elementary Number Theory and its Applications (3rd ed.), Addison-Wesley, 978-0201-57889-8

ISBN

Sengupta, Ambar N. (2012), Representing Finite Groups, A Semisimple Introduction, Springer, 978-1-4614-1232-8

ISBN

Bourbaki, N. (1989), , Springer, ISBN 3-540-64243-9

Algebra I

; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (Second ed.), MIT Press and McGraw-Hill, ISBN 0-262-03293-7. See Section 31.5: The Chinese remainder theorem, pp. 873–876.

Cormen, Thomas H.

Ding, Cunsheng; Pei, Dingyi; Salomaa, Arto (1996), , World Scientific Publishing, pp. 1–213, ISBN 981-02-2827-9

Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography

(1974), Algebra, Graduate Texts in Mathematics, Vol. 73, Springer-Verlag, pp. 131–132, ISBN 978-1-4612-6101-8

Hungerford, Thomas W.

(1997), The Art of Computer Programming, vol. 2: Seminumerical Algorithms (Third ed.), Addison-Wesley, ISBN 0-201-89684-2. See Section 4.3.2 (pp. 286–291), exercise 4.6.2–3 (page 456).

Knuth, Donald

, Encyclopedia of Mathematics, EMS Press, 2001 [1994]

"Chinese remainder theorem"

, "Chinese Remainder Theorem", MathWorld

Weisstein, Eric W.

at PlanetMath.

Chinese Remainder Theorem

(Chinese) – Chinese Text Project

Full text of the Sun-tzu Suan-ching

at ProofWiki