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). 在这里进行浓缩和重新解释;错误属于我们。