Lagmental Vicfred

The Chinese Remainder Theorem Builds One Residue from Local Data by Vicfred

tags: mathematics, congruences, multiplicative order, primitive roots

Pairwise coprime moduli make a system of congruences equivalent to one congruence modulo their product. Keeping the exact identity in view prevents the geometric or probabilistic intuition from drifting.

Statement

Congruences turn divisibility into arithmetic in \(\mathbf Z/n\mathbf Z\). The unit group \((\mathbf Z/n\mathbf Z)^\times\) controls which residues can be cancelled, inverted, or assigned a multiplicative order.

$$ \gcd(m_i,m_j)=1\qquad(i\ne j) $$

The first display fixes the mathematical data. I label it \(\mathsf{data}\) mentally, while the next is the \(\mathsf{claim}\); the bridge between them is the displayed \(\Longrightarrow\), not an automatic implication.

$$ \mathbf Z/(m_1\cdots m_r)\mathbf Z\cong\prod_{i=1}^{r}\mathbf Z/m_i\mathbf Z $$

Worked algebra

The following line is the smallest calculation that still exercises the mechanism. It keeps nested delimiters and the order of operations explicit.

$$ \begin{cases}x\equiv2\pmod3,\\x\equiv3\pmod5,\\x\equiv2\pmod7\end{cases}\quad\Longrightarrow\quad x\equiv23\pmod{105} $$

Conceptual compression

The formula is reusable precisely because it says which pieces are structural and which belong only to the worked example.

$$ \begin{aligned} \mathsf{D}\;&:\quad \gcd(m_i,m_j)=1\qquad(i\ne j),\\[5pt] \mathsf{C}\;&:\quad \mathbf Z/(m_1\cdots m_r)\mathbf Z\cong\prod_{i=1}^{r}\mathbf Z/m_i\mathbf Z. \end{aligned} $$

Caveat

Cancellation modulo \(n\) requires a unit. Dividing both sides by a zero divisor is one of the fastest ways to manufacture a false congruence.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \mathbf Z/(m_1\cdots m_r)\mathbf Z\cong\prod_{i=1}^{r}\mathbf Z/m_i\mathbf Z \end{gathered}} $$

The notation is dense, but it is doing honest work: every delimiter records scope and every index records dependence. Removing one should require a mathematical reason.

This article was posted on Wed 17 September 2014. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.