Number Theory: An Introduction to Mathematics

4 Linear Diophantine Equations 169

thatb=y 1 b 1 +b′for somey 1 ∈ Rand someb′in the moduleM′generated by
a 2 ,...,an.Thesetofallb′which appear in this way is a submoduleL′ofM′.Bythe
induction hypothesis,L′is generated byn−1 elements and henceLis generated byn
elements.

Just as it is useful to define vector spaces abstractly over an arbitrary fieldK,so
it is useful to define modules abstractly over an arbitrary ringR. An abelian groupM,
with the group operation denoted by+,issaidtobeanR-moduleif, with anya∈M
and anyx∈R, there is associated an elementxa∈Mso that the following properties
hold, for alla,b∈Mand allx,y∈R:

(i)x(a+b)=xa+xb,
(ii)(x+y)a=xa+ya,
(iii)(xy)a=x(ya),
(iv) 1a=a.

The proof of Proposition 40 remains valid for modules in this abstract sense. How-
ever, a finitely generated module need not now have a basis. For, even if it is generated
by a single elementa,wemayhavexa=Ofor some nonzerox ∈ R. Neverthe-
less, we are going to show that, ifRis a principal ideal domain, all finitely generated
R-modules can be completely characterized.
Let Rbe a principal ideal domain andMa finitely generatedR-module, with
generatorsa 1 ,...,an,say.ThesetNof allx=(x 1 ,...,xn)∈Rnsuch that

x 1 a 1 +···+xnan=O

is evidently a module inRn. HenceNis finitely generated, by Proposition 40. The
given moduleMis isomorphic to the quotient moduleRn/N.
Letf 1 ,...,fmbe a set of generators forNand lete 1 ,...,enbeabasisforRn.
Then

fj=aj 1 e 1 +···+ajnen ( 1 ≤j≤m),

for someajk∈R. The moduleMis completely determined by the matrixA=(ajk).
However, we can change generators and change bases.
If we put

f′i=vi 1 f 1 +···+vimfm ( 1 ≤i≤m),

whereV=(vij)is an invertiblem×mmatrix, thenf′ 1 ,...,f′mis also a set of gener-
ators forN. If we put

ek=uk 1 e′ 1 +···+ukne′n ( 1 ≤k≤n),

whereU=(uk)is an invertiblen×nmatrix, thene′ 1 ,...,e′nis also a basis forRn.
Moreover

f′i=bi 1 e′ 1 +···+bine′n ( 1 ≤i≤m),

where them×nmatrixB=(bi)isgivenbyB=VAU.
The idea is to chooseVandUso thatBis as simple as possible. This is made
precise in the next proposition, first proved by H.J.S. Smith (1861) forR=Z.The
corresponding matrixSis known as theSmith normal formofA.