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

$$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.]]