maths.free › Abstract Algebra › Rings › An Application to Software Design

An Application to Software Design

The Chinese Remainder Theorem is a result from elementary number theory about the solution of systems of simultaneous congruences. The Chinese mathematician Sun-tsï wrote about the theorem in the first century A.D. This theorem has some interesting consequences in the design of software for parallel processors.

Lemma

Let \(m\) and \(n\) be positive integers such that \(\gcd( m, n) = 1\). Then for \(a, b \in {\mathbb Z}\) the system \[\begin{aligned}x & \equiv a \pmod{m} \\ x & \equiv b \pmod{n}\end{aligned}\] has a solution. If \(x_1\) and \(x_2\) are two solutions of the system, then \(x_1 \equiv x_2 \pmod{mn}\).

Proof

The equation \(x \equiv a \pmod{m}\) has a solution since \(a + km\) satisfies the equation for all \(k \in {\mathbb Z}\). We must show that there exists an integer \(k_1\) such that \[\begin{aligned}\end{aligned}\]. This is equivalent to showing that \[\begin{aligned}\end{aligned}\] has a solution for \(k_1\). Since \(m\) and \(n\) are relatively prime, there exist integers \(s\) and \(t\) such that \(ms + nt = 1\). Consequently, \[\begin{aligned}\end{aligned}\], or \[\begin{aligned}\end{aligned}\]. Now let \(k_1 = (b-a)s\).

To show that any two solutions are congruent modulo \(mn\), let \(c_1\) and \(c_2\) be two solutions of the system. That is, \[\begin{aligned}c_i & \equiv a \pmod{m} \\ c_i & \equiv b \pmod{n}\end{aligned}\] for \(i = 1, 2\). Then \[\begin{aligned}c_2 & \equiv c_1 \pmod{m} \\ c_2 & \equiv c_1 \pmod{n}\end{aligned}\]. Therefore, both \(m\) and \(n\) divide \(c_1 - c_2\). Consequently, \(c_2 \equiv c_1 \pmod{mn}\).

Example

Let us solve the system \[\begin{aligned}x & \equiv 3 \pmod{4} \\ x & \equiv 4 \pmod{5}\end{aligned}\]. Using the Euclidean algorithm, we can find integers \(s\) and \(t\) such that \(4s + 5t = 1\). Two such integers are \(s = 4\) and \(t = -3\). Consequently, \[\begin{aligned}\end{aligned}\].

Special software is required for calculations involving larger integers which cannot be added directly by the machine. By using the Chinese Remainder Theorem we can break down large integer additions and multiplications into calculations that the computer can handle directly. This is especially useful on parallel processing computers which have the ability to run several programs concurrently.

Condensed: the full section is in Judson, Abstract Algebra: Theory and Applications.

이제 너 계산기는 이것을 해결하지 않지만, 그 조각은 계산 가능합니다. 아래의 하나를 시도하거나 자신의 것을 입력하십시오.

자신의 작업을 유지

무료 계정은 모든 수업에 노트를 추가, 당신이 완료 한 기록, 당신이 해결 한 문제를 한 곳에, 그리고 당신이이 페이지에 대해 물어 수업 지도자. 수학 자체는 모두에게 열려 있습니다, 로그인 여부.

가입하기 로그인

여기서 사용된 기호

기호를 탭하면 전체 정의, 이미지 및 각 문자의 의미를 확인할 수 있습니다.

사람들이 묻는 질문

What is a group, in plain words?

A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group. That is where the idea came from.

What is the difference between a ring and a field?

A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.

이 페이지의 일부는 다음에서 변경되었습니다. Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). 여기서 압축하고 다시 설명; 오류는 우리의.

에 더 Abstract Algebra

Groups Subgroups, cosets and Lagrange's theorem Cyclic groups and permutation groups Homomorphisms, normal subgroups and quotient groups Rings and fields Galois theory: why the quintic has no formula