# Computing Using the CRT

In order to explicitly compute an as given by the Theorem 5.1.4, usually one first precomputes elements such that , , etc. Then given any , for , we obtain an with by taking

How to compute the depends on the ring . It reduces to the following problem: Given coprimes ideals , find and such that . If is torsion free and of finite rank as a -module, so , then can be represented by giving a basis in terms of a basis for , and finding such that can then be reduced to a problem in linear algebra over  . More precisely, let  be the matrix whose columns are the concatenation of a basis for  with a basis for . Suppose corresponds to . Then finding such that is equivalent to finding a solution to the matrix equation . This latter linear algebra problem can be solved using Hermite normal form (see [Coh93, §4.7.1]), which is a generalization over of reduced row echelon form.

[[rewrite this to use Sage.]]

Subsections
William Stein 2012-09-24