Computing Using the CRT

In order to explicitly compute an $ a$ as given by the Theorem 5.1.4, usually one first precomputes elements $ v_1, \ldots, v_r \in R$ such that $ v_1\mapsto (1,0,\ldots, 0)$, $ v_2\mapsto (0,1,\ldots, 0)$, etc. Then given any $ a_n \in R$, for $ n=1,\ldots,r$, we obtain an $ a\in R$ with $ a_n\equiv a\pmod{I_n}$ by taking

$\displaystyle a = a_1 v_1 + \cdots + a_r v_r.

How to compute the $ v_i$ depends on the ring $ R$. It reduces to the following problem: Given coprimes ideals $ I,J\subset R$, find $ x\in I$ and $ y\in J$ such that $ x+y=1$. If $ R$ is torsion free and of finite rank as a $ \mathbf {Z}$-module, so $ R\approx \mathbf{Z}^n$, then $ I,J$ can be represented by giving a basis in terms of a basis for $ R$, and finding $ x,y$ such that $ x+y=1$ can then be reduced to a problem in linear algebra over  $ \mathbf {Z}$. More precisely, let $ A$ be the matrix whose columns are the concatenation of a basis for $ I$ with a basis for $ J$. Suppose $ v\in \mathbf{Z}^n$ corresponds to $ 1\in\mathbf{Z}^n$. Then finding $ x,y$ such that $ x+y=1$ is equivalent to finding a solution $ z\in \mathbf{Z}^n$ to the matrix equation $ Az = v$. This latter linear algebra problem can be solved using Hermite normal form (see [Coh93, §4.7.1]), which is a generalization over $ \mathbf {Z}$ of reduced row echelon form.

[[rewrite this to use Sage.]]

William Stein 2012-09-24