108 II Divisibility
Since the distinct squares inZ( 4 )are 0 and 1, it follows that an integera≡3mod4
cannot be represented as the sum of two squares of integers. Similarly, since the distinct
squares inZ( 8 )are 0,1,4, an integera≡7 mod 8 cannot be represented as the sum of
three squares of integers.
The oldest known work on number theory is a Babylonian cuneiform text, from at
least as early as 1600 B.C., which contains a list of right-angled triangles whose side
lengths are all exact multiples of the unit length. By Pythagoras’ theorem, the problem
is to find positive integersx,y,zsuch that
x^2 +y^2 =z^2.For example, 3, 4 ,5and5, 12 ,13 are solutions. The number of solutions listed sug-
gests that the Babylonians not only knew the theorem of Pythagoras, but also had some
rule for finding suchPythagorean triples. There are in fact infinitely many, and a rule
for finding them all is given by Euclid in hisElements(Book X, Lemma 1 following
Proposition 28). This rule will now be derived.
We may assume thatxandyare relatively prime since, ifx,y,zis a Pythagorean
triple for whichxandyhave greatest common divisord,thend^2 |z^2 and henced|z,
so thatx/d,y/d,z/dis also a Pythagorean triple. Ifxandyare relatively prime, then
they are not both even and without loss of generality we may assume thatxis odd. If
ywere also odd, we would have
z^2 =x^2 +y^2 ≡ 1 + 1 ≡2mod4,which is impossible. Henceyis even andzis odd. Then 2 is a common divisor of
z+xandz−x, and is actually their greatest common divisor, since(x,y)=1 implies
(x,z)=1. Since
(y/ 2 )^2 =(z+x)/ 2 ·(z−x)/ 2and the two factors on the right are relatively prime, they are also squares:
(z+x)/ 2 =a^2 ,(z−x)/ 2 =b^2 ,wherea>b>0and(a,b)=1. Then
x=a^2 −b^2 , y= 2 ab, z=a^2 +b^2.Moreoveraandbcannot both be odd, sincezis odd.
Conversely, ifx,y,zare defined by these formulas, whereaandbare relatively
prime positive integers witha>band eitheraorbeven, thenx,y,zis a Pythagorean
triple. Moreoverxis odd, sincezis odd andyeven, and it is easily verified that
(x,y)=1. For givenxandz,a^2 andb^2 are uniquely determined, and henceaandb
are also. Thus different couplesa,bgive different solutionsx,y,z.
To return to congruences, we now consider the structure of the ringZ(m).If
a≡a′modmand(a,m)=1, then also(a′,m)=1. Hence we may speak of an
element ofZ(m)as being relatively prime tom. The set of all elements ofZ(m)which
are relatively prime tomwill be denoted byZ×(m).Ifais aunitof the ringZ(m),then
clearlya∈Z×(m). The following proposition shows that, conversely, ifa∈Z×(m),then
ais a unit of the ringZ(m).