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