Chinese remainder theorem
Chinese remainder theorem (Redirected from Linear congruence theorem) Jump to navigation Jump to search Sun-tzu's original formulation: x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) with the solution x = 23 + 105k, with k an integer 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 Sun-tzu in the Sun-tzu Suan-ching in the 3rd 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.
Contents 1 History 2 Statement 3 Proof 3.1 Uniqueness 3.2 Existence (first proof) 3.3 Existence (constructive proof) 3.3.1 Case of two moduli 3.3.2 General case 3.4 Existence (direct construction) 4 Computation 4.1 Systematic search 4.2 Search by sieving 4.3 Using the existence construction 4.4 As a linear Diophantine system 5 Over principal ideal domains 6 Over univariate polynomial rings and Euclidean domains 6.1 Lagrange interpolation 6.2 Hermite interpolation 7 Generalization to non-coprime moduli 8 Generalization to arbitrary rings 8.1 Interpretation in terms of idempotents 9 Applications 9.1 Sequence numbering 9.2 Fast Fourier transform 9.3 Encryption 9.4 Range ambiguity resolution 9.5 Decomposition of surjections of finite abelian groups 9.6 Dedekind's theorem 10 See also 11 Notes 12 References 13 Further reading 14 External links History The earliest known statement of the theorem, as a problem with specific numbers, appears in the 3rd-century book Sun-tzu Suan-ching by the Chinese mathematician Sun-tzu:[1] There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?[2] Sun-tzu's work contains neither a proof nor a full algorithm.[3] What amounts to an algorithm for solving this problem was described by Aryabhata (6th century).[4] Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century), and appear in Fibonacci's Liber Abaci (1202).[5] The result was later generalized with a complete solution called Da-yan-shu (大衍術) in Ch'in Chiu-shao's 1247 Mathematical Treatise in Nine Sections (數書九章, Shu-shu Chiu-chang)[6] which was translated into English in early 19th century by British missionary Alexander Wylie.[7] The Chinese remainder theorem appears in Gauss's 1801 book Disquisitiones Arithmeticae.[8] The notion of congruences was first introduced and used by Carl Friedrich Gauss in his Disquisitiones Arithmeticae of 1801.[9] Gauss illustrates the Chinese remainder theorem on a problem involving calendars, namely, "to find the years that have a certain period number with respect to the solar and lunar cycle and the Roman indiction."[10] Gauss introduces a procedure for solving the problem that had already been used by Leonhard Euler but was in fact an ancient method that had appeared several times.[11] Statement Let n1, ..., nk be integers greater than 1, which are often called moduli or divisors. Let us denote by N the product of the ni.
The Chinese remainder theorem asserts that if the ni are pairwise coprime, and if a1, ..., ak are integers such that 0 ≤ ai < ni for every i, then there is one and only one integer x, such that 0 ≤ x < N and the remainder of the Euclidean division of x by ni is ai for every i. This may be restated as follows in terms of congruences: If the {displaystyle n_{i}} are pairwise coprime, and if a1, ..., ak are any integers, then the system {displaystyle {begin{aligned}x&equiv a_{1}{pmod {n_{1}}}\&,,,vdots \x&equiv a_{k}{pmod {n_{k}}},end{aligned}}} has a solution, and any two solutions, say x1 and x2, are congruent modulo N, that is, x1 ≡ x2 (mod N ).[12] In abstract algebra, the theorem is often restated as: if the ni are pairwise coprime, the map {displaystyle x{bmod {N}};mapsto ;(x{bmod {n}}_{1},,ldots ,,x{bmod {n}}_{k})} defines a ring isomorphism[13] {displaystyle mathbb {Z} /Nmathbb {Z} cong mathbb {Z} /n_{1}mathbb {Z} times cdots times mathbb {Z} /n_{k}mathbb {Z} } between the ring of integers modulo N and the direct product of the rings of integers modulo the ni. This means that for doing a sequence of arithmetic operations in {displaystyle mathbb {Z} /Nmathbb {Z} ,} one may do the same computation independently in each {displaystyle mathbb {Z} /n_{i}mathbb {Z} } and then get the result by applying the isomorphism (from the right to the left). This may be much faster than the direct computation if N and the number of operations are large. This is widely used, under the name multi-modular computation, for linear algebra over the integers or the rational numbers. The theorem can also be restated in the language of combinatorics as the fact that the infinite arithmetic progressions of integers form a Helly family.[14] Proof The existence and the uniqueness of the solution may be proven independently. However, the first proof of existence, given below, uses this uniqueness. Uniqueness Suppose that x and y are both solutions to all the congruences. As x and y give the same remainder, when divided by ni, their difference x − y is a multiple of each ni. As the ni are pairwise coprime, their product N divides also x − y, and thus x and y are congruent modulo N. If x and y are supposed to be non-negative and less than N (as in the first statement of the theorem), then their difference may be a multiple of N only if x = y. Existence (first proof) The map {displaystyle x{bmod {N}}mapsto (x{bmod {n}}_{1},ldots ,x{bmod {n}}_{k})} maps congruence classes modulo N to sequences of congruence classes modulo ni. The proof of uniqueness shows that this map is injective. As the domain and the codomain of this map have the same number of elements, the map is also surjective, which proves the existence of the solution. This proof is very simple but does not provide any direct way for computing a solution. Moreover, it cannot be generalized to other situations where the following proof can. Existence (constructive proof) Existence may be established by an explicit construction of x.[15] This construction may be split into two steps, firstly by solving the problem in the case of two moduli, and the second one by extending this solution to the general case by induction on the number of moduli. Case of two moduli We want to solve the system: {displaystyle {begin{aligned}x&equiv a_{1}{pmod {n_{1}}}\x&equiv a_{2}{pmod {n_{2}}},end{aligned}}} where {displaystyle n_{1}} and {displaystyle n_{2}} are coprime. Bézout's identity asserts the existence of two integers {displaystyle m_{1}} and {displaystyle m_{2}} such that {displaystyle m_{1}n_{1}+m_{2}n_{2}=1.} The integers {displaystyle m_{1}} and {displaystyle m_{2}} may be computed by the extended Euclidean algorithm. A solution is given by {displaystyle x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}.} Indeed, {displaystyle {begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},end{aligned}}} implying that {displaystyle xequiv a_{1}{pmod {n_{1}}}.} The second congruence is proved similarly, by exchanging the subscripts 1 and 2. General case Consider a sequence of congruence equations: {displaystyle {begin{aligned}x&equiv a_{1}{pmod {n_{1}}}\&vdots \x&equiv a_{k}{pmod {n_{k}}},end{aligned}}} where the {displaystyle n_{i}} are pairwise coprime. The two first equations have a solution {displaystyle a_{1,2}} provided by the method of the previous section. The set of the solutions of these two first equations is the set of all solutions of the equation {displaystyle xequiv a_{1,2}{pmod {n_{1}n_{2}}}.} As the other {displaystyle n_{i}} are coprime with {displaystyle n_{1}n_{2},} this reduces solving the initial problem of k equations to a similar problem with {displaystyle k-1} equations. Iterating the process, one gets eventually the solutions of the initial problem. Existence (direct construction) For constructing a solution, it is not necessary to make an induction on the number of moduli. However, such a direct construction involves more computation with large numbers, which makes it less efficient and less used. Nevertheless, Lagrange interpolation is a special case of this construction, applied to polynomials instead of integers. Let {displaystyle N_{i}=N/n_{i}} be the product of all moduli but one. As the {displaystyle n_{i}} are pairwise coprime, {displaystyle N_{i}} and {displaystyle n_{i}} are coprime. Thus Bézout's identity applies, and there exist integers {displaystyle M_{i}} and {displaystyle m_{i}} such that {displaystyle M_{i}N_{i}+m_{i}n_{i}=1.} A solution of the system of congruences is {displaystyle x=sum _{i=1}^{k}a_{i}M_{i}N_{i}.} In fact, as {displaystyle N_{j}} is a multiple of {displaystyle n_{i}} for {displaystyle ineq j,} we have {displaystyle xequiv a_{i}M_{i}N_{i}equiv a_{i}(1-m_{i}n_{i})equiv a_{i}{pmod {n_{i}}},} for every {displaystyle i.} Computation Consider a system of congruences: {displaystyle {begin{aligned}x&equiv a_{1}{pmod {n_{1}}}\&vdots \x&equiv a_{k}{pmod {n_{k}}},\end{aligned}}} where the {displaystyle n_{i}} are pairwise coprime, and let {displaystyle N=n_{1}n_{2}cdots n_{k}.} In this section several methods are described for computing the unique solution for {displaystyle x} , such that {displaystyle 0leq x
This method works well for hand-written computation with a product of moduli that is not too big. However, it is much slower than other methods, for very large products of moduli. Although dramatically faster than the systematic search, this method also has an exponential time complexity and is therefore not used on computers.
Using the existence construction The constructive existence proof shows that, in the case of two moduli, the solution may be obtained by the computation of the Bézout coefficients of the moduli, followed by a few multiplications, additions and reductions modulo {displaystyle n_{1}n_{2}} (for getting a result in the interval {displaystyle (0,n_{1}n_{2}-1)} ). As the Bézout's coefficients may be computed with the extended Euclidean algorithm, the whole computation, at most, has a quadratic time complexity of {displaystyle O((s_{1}+s_{2})^{2}),} where {displaystyle s_{i}} denotes the number of digits of {displaystyle n_{i}.} For more than two moduli, the method for two moduli allows the replacement of any two congruences by a single congruence modulo the product of the moduli. Iterating this process provides eventually the solution with a complexity, which is quadratic in the number of digits of the product of all moduli. This quadratic time complexity does not depend on the order in which the moduli are regrouped. One may regroup the two first moduli, then regroup the resulting modulus with the next one, and so on. This strategy is the easiest to implement, but it also requires more computation involving large numbers.
Another strategy consists in partitioning the moduli in pairs whose product have comparable sizes (as much as possible), applying, in parallel, the method of two moduli to each pair, and iterating with a number of moduli approximatively divided by two. This method allows an easy parallelization of the algorithm. Also, if fast algorithms (that is, algorithms working in quasilinear time) are used for the basic operations, this method provides an algorithm for the whole computation that works in quasilinear time.
On the current example (which has only three moduli), both strategies are identical and work as follows.
Bézout's identity for 3 and 4 is {displaystyle 1times 4+(-1)times 3=1.} Putting this in the formula given for proving the existence gives {displaystyle 0times 1times 4+3times (-1)times 3=-9} for a solution of the two first congruences, the other solutions being obtained by adding to −9 any multiple of 3 × 4 = 12. One may continue with any of these solutions, but the solution 3 = −9 +12 is smaller (in absolute value) and thus leads probably to an easier computation Bézout identity for 5 and 3 × 4 = 12 is {displaystyle 5times 5+(-2)times 12=1.} Applying the same formula again, we get a solution of the problem: {displaystyle 5times 5times 3+12times (-2)times 4=-21.} The other solutions are obtained by adding any multiple of 3 × 4 × 5 = 60, and the smallest positive solution is −21 + 60 = 39.
As a linear Diophantine system The system of congruences solved by the Chinese remainder theorem may be rewritten as a system of linear Diophantine equations: {displaystyle {begin{aligned}x&=a_{1}+x_{1}n_{1}\&vdots \x&=a_{k}+x_{k}n_{k},end{aligned}}} where the unknown integers are {displaystyle x} and the {displaystyle x_{i}.} Therefore, every general method for solving such systems may be used for finding the solution of Chinese remainder theorem, such as the reduction of the matrix of the system to Smith normal form or Hermite normal form. However, as usual when using a general algorithm for a more specific problem, this approach is less efficient than the method of the preceding section, based on a direct use of Bézout's identity.
Over principal ideal domains 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 {displaystyle 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.
Over univariate polynomial rings and Euclidean domains The statement in terms of remainders given in § Theorem statement cannot be generalized to any principal ideal domain, but its generalization to Euclidean domains is straightforward. The univariate polynomials over a field is the typical example of a Euclidean domain which is not the integers. Therefore, we state the theorem for the case of the ring {displaystyle R=K[X]} for a field {displaystyle K.} For getting the theorem for a general Euclidean domain, it suffices to replace the degree by the Euclidean function of the Euclidean domain.
The Chinese remainder theorem for polynomials is thus: Let {displaystyle P_{i}(X)} (the moduli) be, for {displaystyle i=1,dots ,k} , pairwise coprime polynomials in {displaystyle R=K[X]} . Let {displaystyle d_{i}=deg P_{i}} be the degree of {displaystyle P_{i}(X)} , and {displaystyle D} be the sum of the {displaystyle d_{i}.} If {displaystyle A_{i}(X),ldots ,A_{k}(X)} are polynomials such that {displaystyle A_{i}(X)=0} or {displaystyle deg A_{i}
Si quieres conocer otros artículos parecidos a Chinese remainder theorem puedes visitar la categoría Chinese mathematical discoveries.
Deja una respuesta