Number Theory: An Introduction to Mathematics

166 III More on Divisibility

By=c.

But the latter system is soluble if and only ifcis an integral linear combination of the
firstrcolumnsb 1 ,...,brofB.Sinceb 1 ,...,brare linearly independent, they form
abasisforL.
To determine if a given systemAx=cis soluble, we may use the customary
methods of linear algebra over the fieldQof rational numbers to test ifcis linearly
dependent onb 1 ,...,br; then express it as a linear combination ofb 1 ,...,br,and
finally check thatthe coefficientsy 1 ,...,yrare all integers. The solutions of the orig-
inal system are given byx=Uy,whereyis any vector inZnwhose firstrcoordinates
arey 1 ,...,yr.
IfM 1 andM 2 are modules inZm,theirintersectionM 1 ∩M 2 is again a module.
The set of alla∈Zmsuch thata=a 1 +a 2 for somea 1 ∈M 1 anda 2 ∈M 2 is also a
module, which will be denoted byM 1 +M 2 and called thesumofM 1 andM 2 .IfM 1
andM 2 are finitely generated, thenM 1 +M 2 is evidently finitely generated. We will
show thatM 1 ∩M 2 is also finitely generated.
SinceM 1 +M 2 is a finitely generated module inZm, it has a basisa 1 ,...,an.Since
M 1 andM 2 are contained inM 1 +M 2 , their generatorsb 1 ,...,bpandc 1 ,...,cqhave
the form

bi=

∑n

k= 1

ukiak,

cj=

∑n

k= 1

vkjak,

for someuki,vkj∈Z.Thena∈M 1 ∩M 2 if and only if

a=

∑p

i= 1

yibi=

∑q

j= 1

zjcj

for someyi,zj∈Z.Sincea 1 ,...,anis a basis forM 1 +M 2 , this is equivalent to

∑p

i= 1

ukiyi=

∑q

j= 1

vkjzj

or, in matrix notation,By=Cz. But this is equivalent to the homogeneous system
Ax=O,where

A=(B−C), x=

(

y

z

)

,

and by Proposition 36 the module of solutions of this system has a finite basis.
Suppose the modulesM 1 ,M 2 ⊆Zmare generated by the columns of them×n 1 ,
m×n 2 matricesA 1 ,A 2. EvidentlyM 2 is a submodule ofM 1 if and only if each
column ofA 2 can be expressed as a linear combination of the columns ofA 1 ,i.e.if
and only if there exists ann 1 ×n 2 matrixXsuch that