Decision problem about the existence of solution for an integer matrix equation Given $A,B,C \ $ integer matrices of dimensions $l \times m$, $l \times n$ and $l \times m$, we want to decide (algorithmically) about the existence of $X$ (unimodular) and $Y \ $ integer matrices such that:
$$
AX + B Y = C
$$
Writing the previous equation by blocks
$$
\left(
\begin{array}{cc}
A \mid B
\end{array}
\right)
\left(
\frac{X}{Y}
\right)
= C
$$
you can use the Smith normal form on $(A\mid B)$ to easily decide about the existence of an integer matrix $\left( \frac{X}{Y} \right)$ satisfying the equation. But what about the unimodularity of $X$?
 A: I may be wrong, but doesn't it follow from the effective version of a Borel-Harish-Chandra theorem proved by Grunewald and Segal? In your case, you have a space of $l\times m$ matrices, and a subspace of matrices of the form $BY$. Let $L$ be the factor-space. The (algebraic) group $SL_n({\mathbb R})$ acts on this space naturally and you need to check that two elements are in the same orbit of $SL_n({\mathbb Z})$. Borel-Harish-Chandra says that there is a fundamental domain of the action of $SL_n({\mathbb Z})$, and Grunewald and Segal  say how to find it, and how to check if two elements are in the same orbit (i.e. in the orbit of the same element of the fundamental domain). Perhaps the specialists (I saw Michael Borovoi on MO) can correct me if I am wrong. 
Here is the reference to Grunewald and Segal: Grunewald, Fritz; Segal, Daniel
Some general algorithms. I. Arithmetic groups. Ann. of Math. (2) 112 (1980), no. 3, 531–583.
The proof of Grunewald and Segal is in fact quite difficult. But it provides the easiest known solution to the following problem that is similar to yours. Let $A,B, A',B'$ be two pairs of $n\times n$ matrices over $\mathbb{Z}$. Find (if it exists) a matrix $C$ from $SL_n(\mathbb{Z})$ such that $AC=CA'$ and $BC=CB'$ (you can write it as one matrix equation as in the question: 
$
(A\mid B) C= C(A'\mid B')
$
). This problem is called ``multiple conjugacy" problem for matrices, and was open for quite some time until Grunewald and Segal solved it. I do not know any simpler solution of that problem.
The solvability of the multiple conjugacy problem for matrices implies, in particular, solvability of the isomorphism problem for nilpotent groups and for commutative monoids. Both were open problems for quite some time.
