4 Linear Diophantine Equations 161Proposition 32If m> 1 ,thenN:= 2 m+ 1 is prime if and only if 3 (N−^1 )/^2 + 1 is
divisible by N.
Proof Suppose first thatNdividesa(N−^1 )/^2 +1 for some integera.Ifpis any prime
divisor ofN,thena(N−^1 )/^2 ≡−1modpand henceaN−^1 ≡1modp. Thus, sincep
is necessarily odd, the order ofainF×pdividesN− 1 = 2 m, but does not divide
(N− 1 )/ 2 = 2 m−^1. Hence the order ofamust be exactly 2m. Consequently, by
Lemma II.31 withG=F×p,2mdividesp−1. Thus
2 m≤p− 1 ≤N− 1 = 2 m,which implies thatN=pis prime.
To prove the converse we use the law of quadratic reciprocity. SupposeN=p
is prime. Thenp > 3, sincem > 1. From 2 ≡−1 mod 3 we obtainp ≡
(− 1 )m+1 mod 3. Since 3p, it follows thatp≡−1 mod 3. Thuspis a quadratic
non-residue of 3. Butp≡1 mod 4, sincem>1. Consequently, by the law of quadratic
reciprocity, 3 is a quadratic non-residue ofp. Hence, by Euler’s criterion, 3(p−^1 )/^2 ≡
−1modp.
By means of Proposition 32 it has been shown thatF 14 is composite, even though
no nontrivial factors are known!
4 Linear Diophantine Equations
ADiophantine equationis an algebraic equation with integer coefficients of which the
integer solutions are required. The name honours Diophantus of Alexandria (3rd cen-
tury A.D.), who solved many problems of this type, although the surviving books of
hisArithmeticado not treat the linear problems with which we will be concerned.
We wish to determine integersx 1 ,...,xnsuch that
a 11 x 1 +···+a 1 nxn=c 1
a 21 x 1 +···+a 2 nxn=c 2
···
am 1 x 1 +···+amnxn=cm,where the coefficientsajkand the right sidescjare given integers( 1 ≤ j ≤m,
1 ≤k≤n). We may write the system, in matrix notation, as
Ax=c.The problem may also be put geometrically. A nonempty setM⊆Zmis said to be
aZ–module,orsimplyamodule,ifa,b∈Mandx,y∈Zimplyxa+yb∈M.
For example, ifa 1 ,...,anis a finite subset ofZm, then the setMof all linear com-
binationsx 1 a 1 +···+xnanwithx 1 ,...,xn∈Zis a module, the modulegeneratedby
a 1 ,...,an.Ifwetakea 1 ,...,anto be the columns of the matrixA,thenMis the set
of all vectorsAxwithx∈Znand the systemAx=cis soluble if and only ifc∈M.