162 III More on Divisibility
If a moduleMis generated by the elementsa 1 ,...,an, then it is also generated by
the elementsb 1 ,...,bn,where
bk=u 1 ka 1 +···+unkan (ujk∈Z:1≤j,k≤n),if the matrixU =(ujk)is invertible. Here ann×nmatrixUof integers is said to
beinvertibleif there exists ann×nmatrixU−^1 of integers such thatU−^1 U=Inor,
equivalently,UU−^1 =In.
For example, ifax+by=1, then the matrix
U=
(
ab
−yx)
is invertible, with inverse
U−^1 =
(
x −b
ya)
.
It may be shown, although we will not use it, that ann×nmatrixUis invertible if
and only if its determinant detUis aunit,i.e.detU=±1. Under matrix multiplica-
tion, the set of all invertiblen×nmatrices of integers is a group, usually denoted by
GLn(Z).
To solve the linear Diophantine systemAx=cwe replace it by a systemBy=c,
whereB=AUfor some invertible matrixU. The idea is to chooseUso thatBhas
such a simple form thatycan be determined immediately, and thenx=Uy.
We will use the elementary fact that interchanging two columns of a matrixA,or
adding an integral multiple of one column to another column, is equivalent to postmul-
tiplyingAby a suitable invertible matrixU. In factUis obtained by performing the
same column operation on the identity matrixIn. In the following discussion ‘matrix’
will mean ‘matrix with entries fromZ’.
Proposition 33If A=(a 1 ···an)is a 1 ×n matrix, then there exists an invertible
n×n matrix U such that
AU=(d 0 ··· 0 )if and only if d is a greatest common divisor of a 1 ,...,an.
Proof Suppose first that there exists such a matrixU.Since
A=(d 0 ··· 0 )U−^1 ,dis a common divisor ofa 1 ,...,an. On the other hand,
d=a 1 b 1 +···+anbn,whereb 1 ,...,bnis the first column ofU. Hence any common divisor ofa 1 ,...,an
dividesd. Thusdis a greatest common divisor ofa 1 ,...,an.
Suppose next thata 1 ,...,anhave greatest common divisord. Since there is noth-
ingtodoifn=1, we assumen>1 and use induction onn.Thenifd′is the greatest