<< стр. 10(всего 13)СОДЕРЖАНИЕ >>
11.7. n = 4, F = R. 11.8. n = 3, F = GF(4).
11.9. n = 2, F = Q(i). 11.10. n = 5, F = Z3 .
For Exercises 11.11 to 11.13, in each case, п¬Ѓnd a polynomial in F [x] with r as
a root.
в€љ в€љ
11.11. r = 2 + 6, F = Q.
11.12. r = ПЂ + ei, F = R.
в€љв€љ
11.13. r = 3 3/ 2, F = Q.
11.14. Show that Оё = 2kПЂ/7 satisп¬Ѓes the equation cos 4Оё в€’ cos 3Оё = 0 for each
integer k. Hence п¬Ѓnd an irreducible polynomial over Q with cos(2ПЂ/7)
as a root.
11.15. Prove that the algebraic numbers

A = {x в€€ C|x is algebraic over Q}

form a subп¬Ѓeld of C.
11.16. Assuming the fundamental theorem of algebra, prove that every polyno-
mial in A has a root in A.
For Exercises 11.17 to 11.25, Calculate the degrees.
в€љ
11.17. [Q( 3 7) : Q]. 11.18. [C : Q].
в€љ
11.20. [C : R( в€’7)].
11.19. [Q(i, 3i) : Q].
в€љ
11.21. [Z3 [x]/(x 2 + x + 2) : Z3 ]. 11.22. [Q(i, 2) : Q].
11.23. [A : Q]. 11.24. [C : A].
11.25. [Z3 (t) : Z3 ], where Z3 (t) is the п¬Ѓeld of rational functions in t over Z3 .
в€љ
11.26. Prove that x 2 в€’ 2 is irreducible over Q( 3).
For Exercises 11.27 to 11.32, п¬Ѓnd the inverses of the elements in the given п¬Ѓelds.
Each п¬Ѓeld is a п¬Ѓnite extension F (О±). Express your answers in the form a0 + a1 О± +
В· В· В· + anв€’1 О± nв€’1 , where ai в€€ F and [F (О±) : F ] = n.
в€љ в€љ
11.27. 1 + 3 2 in Q( 3 2).
в€љ в€љ в€љ
11.28. 4 5 + 5 in Q( 4 5).
11.29. 5 + 6П‰ in Q(П‰), where П‰ is a complex cube root of 1.
234 11 FIELD EXTENSIONS

11.30. 2 в€’ 3i in Q(i).
11.31. О± in GF(32) = Z2 (О±), where О± 5 + О± 2 + 1 = 0.
11.32. О± in GF(27) = Z3 (О±), where О± 3 + О± 2 + 2 = 0.
For Exercises 11.33 to 11.40, п¬Ѓnd the characteristic of the rings. Which of these
are п¬Ѓelds?
Z2 Г— Z2 . 11.34. Z3 Г— Z4 .
11.33.
11.36. Z Г— Z2 .
11.35. GF(49).
в€љ
Q( 7).
3
11.37. 11.38. M2 (Z5 ).
Q Г— Z3 .
11.39. 11.40. GF(4)[x].
Let R be any ring and n a positive integer. Prove that In = {na|a в€€ R}
11.41.
is an ideal of R and that the characteristic of R/In divides n.
Let M be a п¬Ѓnite subgroup of the multiplicative group F в€— of any inп¬Ѓnite
11.42.
п¬Ѓeld F . Prove that M is cyclic, and give an example to show that F в€—
need not be cyclic.
For what values of m is (Zв€— , В·) cyclic? (This is a difп¬Ѓcult problem; see
11.43. m
Exercises 4.55 to 4.62 for other results on Zв€— .)
m
Let GF(4) = Z2 (О±), where О± + О± + 1 = 0. Find an irreducible quadratic
2
11.44.
in GF(4)[x]. If ОІ is the root of such a polynomial, show that GF(4)(ОІ)
is a Galois п¬Ѓeld of order 16.
(a) Show that there are (p2 в€’ p)/2 monic irreducible polynomials of
11.45.
degree 2 over GF(p). (A polynomial is monic if the coefп¬Ѓcient of
the highest power of the variable is 1.)
(b) Prove that there is a п¬Ѓeld with p 2 elements for every prime p.
11.46. (a) How many monic irreducible polynomials of degree 3 are there over
GF(p)?
(b) Prove that there is a п¬Ѓeld with p 3 elements for every prime p.
в€љв€љ
Find an element О± such that Q( 2, в€’3) = Q(О±).
11.47.
Find all primitive elements in GF(16) = Z2 (О±), where О± 4 + О± +
11.48.
1 = 0.
11.49. Find all the primitive elements in GF(32).
For Exercises 11.50 and 11.51, п¬Ѓnd a primitive polynomial of degree n over the
п¬Ѓeld F.
11.50. n = 2, F = Z5 . 11.51. n = 3, F = Z2 .
11.52. Let g(x) be a polynomial of degree m over Zp . If g(x)|(x k в€’ 1) for
k = p m в€’ 1 and for no smaller k, show that g(x) is irreducible over Zp .
11.53. Prove that x 8 + x в€€ Z2 [x] will split into linear factors over GF(8) but not
over any smaller п¬Ѓeld.
11.54. Let f (x) = 2x 3 + 5x 2 + 7x + 6 в€€ Q[x]. Find a п¬Ѓeld, smaller than the
complex numbers, in which f (x) splits into linear factors.
11.55. If О± and ОІ are roots of x 3 + x + 1 and x 3 + x 2 + 1 в€€ Z2 [x], respectively,
prove that the Galois п¬Ѓelds Z2 (О±) and Z2 (ОІ) are isomorphic.
EXERCISES 235

11.56. (a) If p(x) в€€ Z2 [x], prove that [p(x)]2 = p(x 2 ).
l
(b) If ОІ is a root of p(x) в€€ Z2 [x], prove that ОІ 2 is a root for all l в€€ N.
(c) Let GF(16) = Z2 (О±) where О± 4 + О± + 1 = 0. Find an irreducible poly-
nomial in Z2 [x] with О± 3 as a root.
For Exercises 11.57 and 11.58, solve the simultaneous linear equations in
GF(4 ) = Z2 (О±).
11.57. О±x + (О± + 1)y = О± + 1 11.58. (О± + 1)x + y = О±
x + О±y = 1. x + (О± + 1)y = О± + 1.
11.59. Solve the quadratic equation О±x 2 + (1 + О±)x + 1 = 0 over the п¬Ѓeld
GF(4) = Z2 (О±).
11.60. Let R be any commutative ring of characteristic p, where p is a prime.
p
(a) Show that (a + b)p = a p + bp for all a, b in R. [Hint: If
r
p pв€’1
p
=
denotes the binomial coefп¬Ѓcient, show that
r r в€’1
r
whenever 1 r p.]
(b) If Пѓ : R в†’ R is deп¬Ѓned by Пѓ (a) = a p for all a в€€ R, show that Пѓ is
a ring morphism.
(c) If R = GF(p n ) show that Пѓ is an isomorphism of R (called the Frobe-
nius automorphism).
11.61. If F is a п¬Ѓeld and F в€— is cyclic, show that F is п¬Ѓnite.
11.62. Design a feedback shift register using six delays that has a cycle length
of 63.
11.63. What is the cycle length of the feedback shift register in Figure 11.3?

Figure 11.3

11.64. Design a feedback shift register that has a cycle length of 21.
11.65. Describe the output sequence of the feedback shift register in Figure 11.4
when the registers initially contain the elements shown.

1 0 1
Output

Figure 11.4

11.66. If a feedback shift register with n delays has a cycle length of 2n в€’ 1,
show that the feedback connections must be derived from a primitive
irreducible polynomial of degree n over Z2 .
12
LATIN SQUARES

Latin squares п¬Ѓrst arose with parlor games such as the problem of arranging the
jacks, queens, kings, and aces of a pack of cards in a 4 Г— 4 array so that each row
and each column contains one card from each suit and one card from each rank.
In 1779, Leonard Euler posed the following famous problem of the 36 ofп¬Ѓcers
from six ranks and six regiments. He claimed that it was impossible to arrange
these ofп¬Ѓcers on parade in a 6 Г— 6 square so that each row and each column
contains one ofп¬Ѓcer from each rank and one from each regiment.
Recently, statisticians have found latin squares useful in designing experi-
ments, and mathematicians have found close connections between latin squares
and п¬Ѓnite geometries.

LATIN SQUARES

Let S be a set with n elements. Then a latin square L = (lij ), of order n based
on S, is an n Г— n array of the elements of S such that each element appears
exactly once in each row and once in each column.
For example, Table 12.1 illustrates a latin square of order 3 based on {a, b, c}.

Theorem 12.1. The table for any п¬Ѓnite group (G, +) of order n is a latin square
of order n based on G.

Proof. We write the operation in G as addition, even though the result still
holds if G is not commutative.
Suppose that two elements in one row are equal. Then xi + xj = xi + xk
for some xi , xj , xk в€€ G. Since G is a group, xi has an inverse (в€’xi ) such
that (в€’xi ) + xi = 0. Hence (в€’xi ) + (xi + xj ) = (в€’xi ) + (xi + xk ), and since the
operation is associative, we have xj = xk . Therefore, an element cannot appear
twice in the same row. Similarly, an element cannot appear twice in the same
column, and the table is a latin square.

Modern Algebra with Applications, Second Edition, by William J. Gilbert and W. Keith Nicholson
ISBN 0-471-41451-4 Copyright п›™ 2004 John Wiley & Sons, Inc.

236
LATIN SQUARES 237

TABLE 12.1. Latin
Square
a b c
c a b
b c a

TABLE 12.2. Latin Squares of Order 4
(0, 0) (0, 1) (1, 0) (1, 1) c b a d
(0, 1) (0, 0) (1, 1) (1, 0) d a b c
(1, 0) (1, 1) (0, 0) (0, 1) a d c b
(1, 1) (1, 0) (0, 1) (0, 0) b c d a

Given any latin square, we can permute the rows among themselves and also
the columns among themselves and we still have a latin square. For example, the
addition table for Z2 Г— Z2 is a latin square of order 4. If we interchange the п¬Ѓrst
and third columns and replace (0, 0) by a, (0, 1) by b, (1, 0) by c, and (1, 1)
by d, we obtain another latin square of order 4 based on {a, b, c, d}. These are
illustrated in Table 12.2.
Latin squares are useful in designing statistical experiments because they can
show how an experiment can be arranged so as to reduce the errors without
making the experiment too large or too complicated. See Laywine and Mullen
 for more complete details.
Suppose that you wanted to compare the yields of three varieties of hybrid
corn. You have a rectangular test plot, but you are not sure that the fertility of the
soil is the same everywhere. You could divide up the land into nine rectangular
regions and plant the three varieties, a, b, and c, in the form of the latin square
in Table 12.1. Then if one row were more fertile than the others, the latin square
would reduce the error that this might cause. In fact, if the soil fertility was a
linear function of the coordinates of the plot, the latin square arrangement would
minimize the error.
Of course, the error could be reduced by subdividing the plot into a large
number of pieces and planting the varieties at random. But this would make it
much more difп¬Ѓcult to sow and harvest.

Example 12.2. A smoking machine is used to test the tar content of four brands
of cigarettes; the machine has four ports so that four cigarettes can be smoked
simultaneously. However, the four ports might not be identical and that might
affect the measurements of the tar content. Also, if four runs were made on the
machine, testing one brand at a time, the humidity could change, thus affecting
the results.
Show how to reduce the errors due to the different ports and the different runs
by using a latin square to design the experiment.
238 12 LATIN SQUARES

TABLE 12.3. Design of the
Smoking Experiment
Ports
12 3 4
в†“в†“ в†“ в†“
1в†’ cb a d
2в†’
Runs da b c
4в†’ bc d a

TABLE 12.4 TABLE 12.5
+ ..p ..q..
A B C D E
B A E C D .
C D A E B .
D E B A C r A B
E C D B A .
s B A
.
.

Solution. If a, b, c, d are the four brands, we can use one of the latin squares
of order 4 that we have constructed. Table 12.3 illustrates which brand should
be tested at each port during each of the four runs.
Not all latin squares can be obtained from a group table, even if we allow
permutations of the rows and columns.
Example 12.3. Show that the latin square illustrated in Table 12.4 cannot be
obtained from a group table.
Solution. By Corollary 4.11, all groups of order 5 are cyclic and are isomor-
phic to (Z5 , +). Suppose that the latin square in Table 12.4 could be obtained
from the addition table of Z5 . Since permutations are reversible, it follows that the
rows and columns of this square could be permuted to obtain the table of Z5 . The
four elements in the left-hand top corner would be taken into four elements form-
ing a rectangle in Z5 , as shown in Table 12.5. Then we would have p + r = A,
q + r = B, p + s = B, and q + s = A for some p, q, r, s в€€ Z5 , where p = q
and r = s. Hence p + r = A = q + s and q + r = B = p + s. Adding, we have
p + q + 2r = p + q + 2s and 2r = 2s. Therefore, 6r = 6s, which implies that
r = s in Z5 , which is a contradiction.

ORTHOGONAL LATIN SQUARES
Suppose that in our cornп¬Ѓeld, besides testing the yields of three varieties of corn,
we also wanted to test the effects of three fertilizers on the corn. We could do
ORTHOGONAL LATIN SQUARES 239

TABLE 12.6 TABLE 12.7
aA bB cC
a b c A B C
cB aC bA
c a b B C A
bC cA aB
b c a C A B

this in the same experiment by arranging the fertilizers on the nine plots so that
each of the three fertilizers was used once on each variety of corn and so that
the different fertilizers themselves were arranged in a latin square of order 3.
Let a, b, c be three varieties of corn and A, B, C be three types of fertilizer.
Then the two latin squares in Table 12.6 could be superimposed to form the
design in Table 12.7. In this table, each variety of corn and each type of fertilizer
appears exactly once in each row and in each column. Furthermore, each type
of fertilizer is used exactly once with each variety of corn. This table could be
used to design the experiment. For example, in the top left section of our test
plot, we would plant variety a and use fertilizer A.
Two latin squares of order n are called orthogonal if when the squares
are superimposed, each element of the п¬Ѓrst square occurs exactly once with
each element of the second square. Thus the two latin squares in Table 12.6
are orthogonal.
Although it is easy to construct latin squares of any order, the construction
of orthogonal latin squares can be a difп¬Ѓcult problem. At this point the reader
should try to construct two orthogonal latin squares of order 4.
Going back to our п¬Ѓeld of corn and fertilizers, could we use the same trick
again to test the effect of three insecticides by choosing another latin square of
order 3 orthogonal to the п¬Ѓrst two? It can be proved that it is impossible to
п¬Ѓnd such a latin square (see Exercise 12.5). However, if we have four types of
corn, fertilizer, and insecticide, we show using Theorem 12.5 how they could
be distributed on a 4 Г— 4 plot using three latin squares of order 4 orthogonal to
each other.
If L1 , . . . , Lr are latin squares of order n such that Li is orthogonal to Lj
for all i = j , then {L1 , . . . , Lr } is called a set of r mutually orthogonal latin
squares of order n.
We show how to construct n в€’ 1 mutually orthogonal latin squares of order
n from a п¬Ѓnite п¬Ѓeld with n elements. We know that a п¬Ѓnite п¬Ѓeld has a prime
power number of elements, and we are able to construct such squares for n =
2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, . . . etc.
Let GF(n) = {x0 , x1 , x2 , . . . , xnв€’1 } be a п¬Ѓnite п¬Ѓeld of order n = p m , where
x0 = 0 and x1 = 1. Let L1 = (aij ) be the latin square of order n that is the
1

aij = xi + xj n в€’ 1 and 0 n в€’ 1.
1
for 0 i j

Proposition 12.4. Deп¬Ѓne the squares Lk = (aij ) for 1 n в€’ 1 by
k
k

aij = xk В· xi + xj nв€’1 n в€’ 1.
k
for 0 and 0
i j
240 12 LATIN SQUARES

n в€’ 1 based on GF(n).
Then Lk is a latin square of order n for 1 k

Proof. The difference between two elements in the ith row is

aij в€’ aiq = (xk В· xi + xj ) в€’ (xk В· xi + xq )
k k

= xj в€’ xq = 0 if j = q.

Hence each row is a permutation of GF(n).
The difference between two elements in the j th column is

aij в€’ arj = (xk В· xi + xj ) в€’ (xk В· xr + xj )
k k

= xk В· (xi в€’ xr ) = 0 if i = r since xk = 0 and xi = xr .

Hence each column is a permutation of GF(n) and Lk is a latin square of order n.

Theorem 12.5. With the notation in Proposition 12.4, {L1 , L2 , . . . , Lnв€’1 } is a
mutually orthogonal set of latin squares of order n = p m .

Proof. We have to prove that Lk is orthogonal to Ll for all k = l.
Suppose that when Lk is superimposed on Ll , the pair of elements in the
(i, j )th position is the same as the pair in the (r, q)th position. That is, (aij , aij ) =
k l

(arq , arq ) or aij = arq and aij = arq . Hence xk В· xi + xj = xk В· xr + xq and
k l
k l k l

xl В· xi + xj = xl В· xr + xq . Subtracting, we have (xk в€’ xl ) В· xi = (xk в€’ xl ) В· xr or
(xk в€’ xl ) В· (xi в€’ xr ) = 0. Now the п¬Ѓeld GF(n) has no zero divisors; thus either
xk = xl or xi = xr . Hence either k = l or i = r. But k = l and we know from
Proposition 12.4 that two elements in the same row of Lk or Ll cannot be equal;
therefore, i = r.
This contradiction proves that when Lk and Ll are superimposed, all the pairs
of elements occurring are different. Each element of the п¬Ѓrst square appears n
times and hence must occur with all the n different elements of the second square.
Therefore, Lk is orthogonal to Ll , if k = l.

If we start with Z3 and perform the construction above, we obtain the two
mutually orthogonal latin squares of order 3 given in Table 12.8.

Example 12.6. Construct three mutually orthogonal latin squares of order 4.

TABLE 12.8. Two Orthogonal
Latin Squares
0 1 2 0 1 2
L1 1 L2
2 0 2 0 1
2 0 1 1 2 0
ORTHOGONAL LATIN SQUARES 241

TABLE 12.9. Three Mutually Orthogonal Latin Squares of Order 4
О±2 О±2 О±2
0 1 0 1 0 1
О± О± О±
О±2 О±2 О±2
1 0 0 1 1 0
О± О± О±
L1 L2 L3
О±2 О±2 О±2
0 1 1 0 1 0
О± О± О±
О±2 О±2 О±2
1 0 1 0 0 1
О± О± О±

TABLE 12.10. Superimposed Latin
Squares TABLE 12.11. Sixteen Court Cards
Jв™Ј
aaa bbb ccc ddd Aв™  Kв™¦ Qв™Ґ
Jв™Ґ
bcd adc dab cba Qв™Ј Aв™¦ Kв™
Jв™¦
cdb dca abd bac Qв™  Kв™Ј Aв™Ґ
Jв™
dbc cad bda acb Kв™Ґ Aв™Ј Qв™¦

Solution. Apply the method given in Proposition 12.4 to the Galois п¬Ѓeld
GF(4) = Z2 (О±) = {0, 1, О±, О± 2 }, where О± 2 = О± + 1.
L1 is simply the addition table for GF(4). From the way the square Lk was
constructed in Proposition 12.4, we see that its rows are a permutation of the
rows of L1 . Hence L2 can be obtained by multiplying the п¬Ѓrst column of L1 by
О± and then permuting the rows of L1 so that they start with the correct element.
L3 is also obtained by permuting the rows of L1 so that the п¬Ѓrst column is О± 2
times the п¬Ѓrst column of L1 . These are illustrated in Table 12.9.

If we write a for 0, b for 1, c for О±, and d for О± 2 , and superimpose the three
latin squares, we obtain Table 12.10. Example 12.6 also allows us to solve the
parlor game of laying out the 16 cards that was mentioned at the beginning of the
chapter. One solution, using the squares L2 and L3 in Table 12.9, is illustrated
in Table 12.11.

Example 12.7. A drug company wishes to produce a new cold remedy by com-
bining a decongestant, an antihistamine, and a pain reliever. It plans to test various
combinations of three decongestants, three antihistamines, and three pain reliev-
ers on four groups of subjects each day from Monday to Thursday. Furthermore,
each type of ingredient should also be compared with a placebo. Design this test
so as to reduce the effects due to differences between the subject groups and the
different days.

Solution. We can use the three mutually orthogonal latin squares constructed
in Example 12.6 to design this experimentвЂ”see Table 12.9.
Make up the drugs given to each group using Table 12.12. The letter in the
п¬Ѓrst position refers to the decongestant, the second to the antihistamine, and the
third to the pain reliever. The letter a refers to a placebo, and b, c, and d refer
to the three different types of ingredients.
242 12 LATIN SQUARES

TABLE 12.12. Testing Three Different
Drugs

Mon. Tues. Wed. Thurs.
aaa bbb ccc ddd
A
B
Group cdb dca abd bac
C
D

We recognize EulerвЂ™s problem of the 36 ofп¬Ѓcers on parade mentioned at the
beginning of the chapter as the problem of constructing two orthogonal latin
squares of order 6. Euler not only conjectured that this problem was impossible
to solve, but he also conjectured that it was impossible to п¬Ѓnd two orthogonal
latin squares of order n, whenever n в‰Ў 2 mod 4.
Theorem 12.5 cannot be used to construct two such squares with order congruent
to 2 modulo 4 because the only prime power of this form is 2, and then the theorem
only gives one latin square. In 1899, G. Tarry, by exhaustive enumeration, proved
that the problem of the 36 ofп¬Ѓcers was insoluble. However, in 1959, EulerвЂ™s general
conjecture was shown to be false, and in fact, Bose, Shrikhande, and Parker proved
that there exist at least two orthogonal latin squares of order n, for any n > 6.
Hence Proposition 12.4 is by no means the only way of constructing orthogonal
latin squares. Laywine and Mullen  give a comprehensive survey of all the
known results on latin squares up to the time of the bookвЂ™s publication in 1998.

FINITE GEOMETRIES

The construction in Theorem 12.5 of n в€’ 1 mutually orthogonal latin squares of
order n, when n is a prime power, was п¬Ѓrst discovered by the American mathe-
matician E. H. Moore in 1896, and was rediscovered by the Indian mathematical
statistician R. C. Bose in 1938. (See Section 2.2 of Laywine and Mullin .)
Bose also showed that there is a very close connection between orthogonal latin
squares and geometries with a п¬Ѓnite number of points and lines. These geometries
are called afп¬Ѓne planes.
An afп¬Ѓne plane consists of a set, P , of points, together with a set, L, of
subsets of P called lines. The points and lines must satisfy the following inci-
dence axioms.

(i) Any two distinct points lie on exactly one line.
(ii) For each line l and point x not on l, there exists a unique line m containing
x and not meeting l.
(iii) There exist three points not lying on a line.

We can deп¬Ѓne an equivalence relation of parallelism, / /, on the set of lines L,
by deп¬Ѓning l//m if l = m or l and m contain no common point. Axiom (ii) then
states that through each point there is a unique line parallel to any other line. The
FINITE GEOMETRIES 243

points and lines in the euclidean plane R2 form such a geometry with an inп¬Ѓnite
number of points.
If the geometry has only a п¬Ѓnite number of points, it can be shown that there
exists an integer n such that the geometry contains n2 points and n2 + n lines,
and that each line contains n points, while each point lies on n + 1 lines. Such a
п¬Ѓnite geometry is called an afп¬Ѓne plane of order n. In an afп¬Ѓne plane of order
n there are n + 1 parallelism classes (see Exercises 12.12 and 12.13).
Figure 12.1 shows an afп¬Ѓne plane of order 2 in which P = {a, b, c, d} and
L = {{a, b}, {c, d}, {a, c}, {b, c}, {b, d}, {a, d}}.
Bose showed that an afп¬Ѓne plane of order n produces a complete set of n в€’ 1
mutually orthogonal latin squares of order n, and conversely, that each set of
n в€’ 1 mutually orthogonal latin squares of order n deп¬Ѓnes an afп¬Ѓne plane of
order n.

Theorem 12.8. There exists an afп¬Ѓne plane of order n if and only if there exist
n в€’ 1 mutually orthogonal latin squares of order n.

Proof. Suppose that there exists an afп¬Ѓne plane of order n. We coordinatize
the points as follows. Take any line and label the n points as 0, 1, 2, . . . , n в€’ 1.
This is called the x-axis, and the point labeled 0 is called the origin. Choose
any other line through the origin and label the n points 0, 1, 2, . . . , n в€’ 1 with
0 at the origin. This line is called the y-axis. A point of the plane is said to
have coordinates (a, b) if the unique lines through the point parallel to the y and
x-axes meet the axes in points labeled a and b, respectively. This is illustrated
in Figure 12.2.

a b

c d

Figure 12.1. Afп¬Ѓne plane with four points.

y
nв€’1
b (a, b)
1
x
nв€’1
a
0 1

Figure 12.2. Coordinates in an afп¬Ѓne plane.
244 12 LATIN SQUARES

There are n2 ordered pairs (a, b) corresponding to the n2 points of the plane.
These points also correspond to the n2 cells of an n Г— n square where (a, b)
refers to the cell in the ath row and bth column. We п¬Ѓll these cells with numbers
in n в€’ 1 different ways to produce n в€’ 1 mutually orthogonal latin squares of
order n.
Consider any complete set of parallel lines that are not parallel to either axis.
Label the n parallel lines 0, 1, 2, . . . , n в€’ 1 in any manner. Through each point,
there is exactly one of these lines. In the cell (a, b) place the number of the
unique line on which the point (a, b) is found. The numbers in these cells form
a latin square of order n on {0, 1, . . . , n в€’ 1}. No two numbers in the same row
can be the same, because there is only one line through two points in the same
row, namely, the line parallel to the x-axis. Hence each number appears exactly
once in each row and, similarly, once in each column.
There are n в€’ 1 sets of parallelism classes that are not parallel to the axes; each
of these gives rise to a latin square. These n в€’ 1 squares are mutually orthogonal
because each line of one parallel system meets all n of the lines of any other
system. Hence, when two squares are superimposed, each number of one square
occurs once with each number of the second square.
Conversely, suppose that there exists a set of n в€’ 1 mutually orthogonal latin
squares of order n. We can relabel the elements, if necessary, so that these squares
are based on S = {0, 1, 2, . . . , n в€’ 1}. We deп¬Ѓne an afп¬Ѓne plane with S 2 as the
set of points. A set of n points is said to lie on a line if there is a latin square
with the same number in each of the n cells corresponding to these points, or if
the n points all have one coordinate the same. It is straightforward to check that
this is an afп¬Ѓne plane of order n.

Corollary 12.9. There exists an afп¬Ѓne plane of order n whenever n is the power
of a prime.

Proof. This follows from Theorem 12.5.

The only known afп¬Ѓne planes have prime power order. Because of the impos-
sibility of solving EulerвЂ™s ofп¬Ѓcer problem, there are no orthogonal latin squares
of order 6, and hence there is no afп¬Ѓne plane of order 6. In 1988, by means of
a massive computer search, Lam, Thiel, and Swiercz showed that there was no
afп¬Ѓne plane of order 10. See Lam  for the story behind this two-decade search.
By Theorem 12.8, there cannot exist nine mutually orthogonal latin squares of
order 10. However, two mutually orthogonal latin squares of order 10 have been
found, but not three such squares. Computers have also been used to search for
many sets of mutually orthogonal latin squares of low order. See Chapter 2 of
Laywine and Mullen  for further results on mutually orthogonal latin squares.
By the method of Theorem 12.8, we can construct an afп¬Ѓne plane of order n
from the Galois п¬Ѓeld GF(n) whenever n is a prime power. The set of points is

P = GF(n)2 = {(x, y)|x, y в€€ GF(n)}.
MAGIC SQUARES 245

(0, a 2) (1, a 2) (a, a 2) (a 2, a 2)

(a 2, a)
(a, a)
(0, a) (1, a)

(a 2, 1)
(a, 1)
(0, 1) (1, 1)

(a 2, 0)
(0, 0) (1, 0) (a, 0)

Afп¬Ѓne plane of order 4 with the points of the line y = О±x + О± 2 enlarged.
Figure 12.3.

It follows from Proposition 12.4 that a line consists of points satisfying a linear
equation in x and y with coefп¬Ѓcients in GF(n). The slope of a line is deп¬Ѓned in
the usual way and is an element of GF(n) or is inп¬Ѓnite. Two lines are parallel if
and only if they have the same slope.
For example, if GF(4) = Z2 (О±) = {0, 1, О±, О± 2 }, the 16 points of the afп¬Ѓne
plane of order 4 are shown in Figure 12.3. The horizontal lines are of the form

y = constant

and have slope 0, whereas the vertical lines are of the form

x = constant

and have inп¬Ѓnite slope. The line

y = О±x + О± 2

has slope О± and contains the points (0, О± 2 ), (1, 1), (О±, 0) and (О± 2 , О±). This line
is parallel to the lines y = О±x, y = О±x + 1, and y = О±x + О±.
Given an afп¬Ѓne plane of order n, it is possible to construct a projective plane
of order n by adding a вЂњline at inп¬ЃnityвЂќ containing n + 1 points corresponding
to each parallelism class, so that parallel lines intersect on the line at inп¬Ѓnity.
The projective plane of order n has n2 + n + 1 points and n2 + n + 1 lines.
Furthermore, any projective plane gives rise to an afп¬Ѓne plane by taking one line
to be the line at inп¬Ѓnity. Hence the existence of a projective plane of order n is
equivalent to the existence of an afп¬Ѓne plane of the same order.

MAGIC SQUARES

Magic squares have been known for thousands of years, and in times when
particular numbers were associated with mystical ideas, it was natural that a
246 12 LATIN SQUARES

Publisher's Note:
Permission to reproduce this image
online was not granted by the
requested to refer to the printed version

Figure 12.4. вЂњMelancholia,вЂќ an engraving by Albrecht DВЁ rer. In the upper right there is a magic
u
square of order 4 with the date of the engraving, 1514, in the middle of the bottom row. [Courtesy
of Staatliche Museen Kupferstichkabinett, photo by Walter Steinkopf.]

square that displays such symmetry should have been deemed to have magical
properties. Figure 12.4 illustrates an engraving by DВЁ rer, made in 1514, that
u
contains a magic square. Magic squares have no applications, and this section is
included for amusement only.
MAGIC SQUARES 247

A magic square of order n consists of the integers 1 to n2 arranged in an
n Г— n square array so that the row sums, column sums, and corner diagonal sums
are all the same.
The sum of each row must be n(n2 + 1)/2, which is 1/n times the sum of all
the integers from 1 to n2 . For example, in DВЁ rerвЂ™s magic square of Figure 12.4,
u
the sum of each row, column, and diagonal is 34.
It is an interesting exercise to try to construct such squares. We show how to
construct some magic squares from certain pairs of orthogonal latin squares. See
Ball et al.  and Laywine and Mullen  for other methods of constructing
magic squares.
Let K = (kij ) and L = (lij ) be two orthogonal latin squares of order n on the
set S = {0, 1, . . . , n в€’ 1}. Superimpose these two squares to form a square M =
(mij ) in which the elements of M are numbers in the base n, whose п¬Ѓrst digit is
taken from K and whose second digit is taken from L. That is, mij = n В· kij + lij .
Since K and L are orthogonal, all possible combinations of two elements from
S occur exactly once in M. In other words, all the numbers from 0 to n2 в€’ 1
occur in M.
Now add 1 to every element of M to obtain the square M = mij , where
mij = mij + 1.

Lemma 12.10. The square M contains all the numbers between 1 and n2 and
is row and column magic; that is, the sums of each row and of each column are
the same.

Proof. In any row or column of M, each number from 0 to n в€’ 1 occurs
exactly once as the п¬Ѓrst digit and exactly once as the second digit. Hence the
sum is

(0 + 1 + В· В· В· + n в€’ 1)n + (0 + 1 + В· В· В· + n в€’ 1)
= (n + 1)(n в€’ 1)n/2 = n(n2 в€’ 1)/2.

Therefore, each row or column sum of M is n(n2 в€’ 1)/2 + n = n(n2 + 1)/2.

Example 12.11. Construct the square M from the two orthogonal latin squares,
K and L, in Table 12.13.

Solution. Table 12.13 illustrates the superimposed square M in base 3 and in
base 10. By adding one to each element, we obtain the magic square M .

Theorem 12.12. If K and L are orthogonal latin squares of order n on the
set {0, 1, 2, . . . , n в€’ 1} and the sum of each of the diagonals of K and L is
n(n в€’ 1)/2, then the square M derived from K and L is a magic square of
order n.
248 12 LATIN SQUARES

TABLE 12.13. Construction of a Magic
Square of Order 3
1 2 0 0 2 1 10 22 01
0 1 2 2 1 0 02 11 20
2 0 1 1 0 2 21 00 12
M (in base 3)
K L
3 8 1 4 9 2
2 4 6 3 5 7
7 0 5 8 1 6
M (in base 10) M

Proof. Lemma 12.10 shows that the sum of each row and each column is
n(n2 + 1)/2. A similar argument shows that the sum of each diagonal is also
n(n2 + 1)/2.

There are two common ways in which the sum of the diagonal elements of
K and L can equal n(n в€’ 1)/2.

(i) The diagonal is a permutation of {0, 1, . . . , n в€’ 1}.
(ii) If n is odd, every diagonal element is (n в€’ 1)/2.

Both these situations occur in the squares K and L of Table 12.13; thus the
square M , which is constructed from these, is a magic square.

Example 12.13. Construct a magic square of order 4 from two orthogonal latin
squares in Table 12.9.

Solution. By replacing 0, 1, О±, О± 2 by 0, 1, 2, 3, in any order, the squares
L2 and L3 in Table 12.9 satisfy the conditions of Theorem 12.12, because the

TABLE 12.14. Construction of a Magic
Square of Order 4
0 1 2 3 3 2 0 1
2 3 0 1 1 0 2 3
3 2 1 0 2 3 1 0
1 0 3 2 0 1 3 2
L2 L3
03 12 20 31 4 7 9 14
21 30 02 13 10 13 3 8
32 23 11 00 15 12 6 1
10 01 33 22 5 2 16 11
M (in base 4) M
EXERCISES 249

diagonal elements are all different. However, L1 will not satisfy the conditions
of Theorem 12.12, whatever substitutions we make. In L2 , replace 0, 1, О±, О± 2 by
0, 1, 2, 3, respectively, and in L3 replace 0, 1, О±, О± 2 by 3, 2, 0, 1, respectively, to
obtain the squares L2 and L3 in Table 12.14. Combine these to obtain the square
M with entries in base 4. Add 1 to each entry and convert to base 10 to obtain
the magic square M in Table 12.14.

EXERCISES

Construct a latin square of order 7 on {a, b, c, d, e, f, g}.
12.1.
12.2. Construct four mutually orthogonal latin squares of order 5.
12.3. Construct four mutually orthogonal latin squares of order 8.
12.4. Construct two mutually orthogonal latin squares of order 9.
Prove that there are at most (n в€’ 1) mutually orthogonal latin squares of
12.5.
order n. (You can always relabel each square so that the п¬Ѓrst rows are
the same.)
12.6. Let L = (lij ) be a latin square of order l on {1, 2, . . . , l} and M = (mij )
be a latin square of order m on {1, 2, . . . , m}. Describe how to construct
a latin square of order lm on {1, 2, . . . , l} Г— {1, 2, . . . , m} from L and M.
12.7. Is the latin square of Table 12.15 the multiplication table for a group of
order 6 with identity A?

TABLE 12.15
A B C D E F
B A F E C D
C F B A D E
D C E B F A
E D A F B C
F E D C A B

12.8. A chemical company wants to test a chemical reaction using seven differ-
ent levels of catalyst, a, b, c, d, e, f , g. In the manufacturing process, the
raw material comes from the previous stage in batches, and the catalyst
must be added immediately. If there are seven reactors, A, B, C, D, E,
F , G, in which the catalytic reaction can take place, show how to design
the experiment using seven batches of raw material so as to minimize the
effect of the different batches and of the different reactors.
12.9. A supermarket wishes to test the effect of putting cereal on four shelves
at different heights. Show how to design such an experiment lasting four
weeks and using four brands of cereal.
250 12 LATIN SQUARES

12.10. A manufacturer has п¬Ѓve types of toothpaste. He would like to test these
on п¬Ѓve subjects by giving each subject a different type each week for п¬Ѓve
weeks. Each type of toothpaste is identiп¬Ѓed by a different colorвЂ”red,
blue, green, white, or purpleвЂ”and the manufacturer changes the color
code each week to reduce the psychological effect of the color. Show
how to design this experiment.
12.11. Quality control would like to п¬Ѓnd the best type of music to play to its
assembly line workers in order to reduce the number of faulty products.
As an experiment, a different type of music is played on four days in
a week, and on the п¬Ѓfth day no music at all is played. Design such an
experiment to last п¬Ѓve weeks that will reduce the effect of the different
days of the week.
12.12. The relation of parallelism, //, on the set of lines of an afп¬Ѓne plane is
deп¬Ѓned by l//m if and only if l = m or l в€© m = Г˜. Prove that // is an
equivalence relation.
12.13. Let P be the set of points and L be the set of lines of a п¬Ѓnite afп¬Ѓne plane.
(a) Show that the number of points on a line l equals the number of lines
in any parallelism class not containing l.
(b) Deduce that all the lines contain the same number of points.
(c) If each line contains n points, show that the plane contains n2 points
and n2 + n lines, each point lying on n + 1 lines. Show also that there
are n + 1 parallelism classes.
12.14. Find all the lines in the afп¬Ѓne plane of order 3 whose point set is Z2 .
3
Exercises 12.15 to 12.17 refer to the afп¬Ѓne plane of order 9 obtained from GF(9 ) =
Z3 (О±), where О± 2 + 1 = 0 .
12.15. Find the line through (2О±, 1) that is parallel to the line y = О±x + 2 + О±.
12.16. Find the point of intersection of the lines y = x + О± and y = (О± + 1)x +
2О±.
12.17. Find the equation of the line through (0, 2О±) and (2, О± + 1).
12.18. Prove that a magic square of order 3 must have 5 at its center.
12.19. Prove that 1 cannot be a corner element of a magic square of order 3.
12.20. How many different magic squares of order 3 are there?
12.21. How many essentially different magic squares of order 3 are there, that
is, magic squares that cannot be obtained from each other by a symmetry
of the square?
12.22. Is there a magic square of order 2?
12.23. Find two magic squares of order 4 different from the square in
Example 12.18.
12.24. Find a magic square of order 5.
12.25. Find a magic square of order 8.
12.26. Can you construct a magic square with the present year in the last two
squares of the bottom row?
13
GEOMETRICAL
CONSTRUCTIONS

The only geometric instruments used by the ancient Greeks were a straightedge
and a compass. They did not possess reliable graduated rulers or protractors.
However, with these two instruments, they could still perform a wide variety of
constructions; they could divide a line into any number of equal parts, and they
could bisect angles and construct parallel and perpendicular lines. There were
three famous problems that the Greeks could not solve using these methods:
(1) duplication of the cube; that is, given one edge of a cube, construct the edge
of a cube whose volume is double that of the given cube; (2) trisection of any
given angle; and (3) squaring of the circle; that is, given any circle, construct a
square whose area is the same as that of the circle. For centuries, the solution
to these problems eluded mathematicians, despite the fact that large prizes were
offered for their discovery.
It was not until the nineteenth century that mathematicians suspected and, in
fact, proved that these constructions were impossible. In the beginning of that
century, nonexistence proofs began appearing in algebra; it was proved that the
general polynomial equation of degree 5 could not be solved in terms of nth roots
and rational operations. Similar algebraic methods were then applied to these
geometric problems. The geometric problems could be converted into algebraic
problems by determining which multiples of a given length could be constructed
using only straightedge and compass. Some of the classical constructions are
illustrated in Figure 13.1.

CONSTRUCTIBLE NUMBERS

We are interested in those lengths that can be constructed from a given length.
For convenience, we choose our unit of length to be the given length. We see

Modern Algebra with Applications, Second Edition, by William J. Gilbert and W. Keith Nicholson
ISBN 0-471-41451-4 Copyright п›™ 2004 John Wiley & Sons, Inc.

251
252 13 GEOMETRICAL CONSTRUCTIONS

P
P

l

l

Constructing a line through P
Erecting a perpendicular
from P to a line l parallel to a line l

r в€љ2r
r
n
r
r

Constructing в€љ2 times
Dividing a length r into
n equal segments a given length r

Figure 13.1. Geometrical constructions using straightedge and compass.

that we can divide a length into any number of equal parts, and hence we can
construct any rational multiple. However, we can do more than this; we can
в€љ
construct irrational multiples such as 2 by using right-angled triangles.
Given any line segment in the plane, choose rectangular coordinates so that
the lineвЂ™s end points are (0, 0) and (1, 0). Any point in the plane that can be
constructed from this line segment by using a straightedge and compass is called
a constructible point. A real number is called constructible if it occurs as one
coordinate of a constructible point. Points can be constructed by performing the
following allowable operations a п¬Ѓnite number of times. We can:

1. Draw a line through two previously constructed points.
2. Draw a circle with center at a previously constructed point and with radius
equal to the distance between two previously constructed points.
3. Mark the point of intersection of two straight lines.
4. Mark the points of intersection of a straight line and a circle.
5. Mark the points of intersection of two circles.

Theorem 13.1. The set of constructible numbers, K, is a subп¬Ѓeld of R.

Proof. K is a subset of R, so we have to show that it is a п¬Ѓeld. That is, if
a, b в€€ K, we have to show that a + b, a в€’ b, ab, and if b = 0, a/b в€€ K.
CONSTRUCTIBLE NUMBERS 253

B
C
c
b

X A
O
x
a

Figure 13.2. Constructing products and quotients.

If a, b в€€ K, we can mark off lengths a and b on a line to construct lengths
a + b and a в€’ b.
If a, b, c в€€ K, mark off a segment OA of length a on one line and mark off
segments OB and OC of length b and c on another line through O as shown
in Figure 13.2. Draw a line through B parallel to CA and let it meet OA in X.
Triangles OAC and OXB are similar, and if OX = x, then x/a = b/c and so
x = ab/c.
By taking c = 1, we can construct ab, and by taking b = 1, we can construct
a/c. Hence K is a subп¬Ѓeld of R.

Corollary 13.2. K is an extension п¬Ѓeld of Q.

Proof. Since 1 в€€ K and sums and differences of constructible numbers are
constructible, it follows that Z вЉ† K. Since quotients of constructible numbers
are constructible, Q вЉ† K.
в€љ
Proposition 13.3. If k в€€ K and k > 0, then k в€€ K.

Proof. Mark off segments AB and BC of lengths k and 1 on a line. Draw the
circle with diameter AC and construct the perpendicular to AC at B as shown
in Figure 13.3. Let it meet the circle at D and E. Then, by a standard theorem
в€љ
in geometry, AB В· BC = DB В· BE: thus BD = BE = k.
в€љ
4
Example 13.4. 2 is constructible.
в€љ
Solution. We apply the construction of Proposition 13.3 twice to construct 2
в€љ в€љ
2 = 4 2.
and then

We can construct any number that can be written in terms of rational numbers,
в€љв€љ в€љ
в€љ
+, в€’, В·, Г·, and signs. For example, the numbers 1 + 4 5, 2 + 4/5, and
в€љ
3 в€’ 7 are all constructible. If k1 is a positive rational number, all the elements
254 13 GEOMETRICAL CONSTRUCTIONS

D

в€љk

k 1
A C
B
в€љk

E

Figure 13.3. Constructing square roots.

в€љ
of the extension п¬Ѓeld K1 = Q( k1 ) are constructible. K1 has degree 1 or 2 over
в€љ
Q depending on whether k1 is rational or irrational. If k2 is a positive element
в€љ в€љв€љ
of K1 , all the elements of K2 = K1 ( k2 ) = Q( kв€љ k2 ) are constructible, and
1,
[K2 : K1 ] = 1 or 2, depending on whether or not k2 is an element of K1 . We
now show that every constructible number lies in a п¬Ѓeld obtained by repeating
the extensions above.

Theorem 13.5. The number О± is constructible if and only if there exists a
sequence of real п¬Ѓelds K0 , K1 , . . . , Kn such that О± в€€ Kn вЉ‡ Knв€’1 вЉ‡ В· В· В· вЉ‡ K0 =
Q and [Ki : Kiв€’1 ] = 2 for 1 i n.

Proof. Suppose that О± в€€ Kn вЉ‡ Knв€’1 вЉ‡ В· В· В· вЉ‡ K0 = Q, where [Ki : Kiв€’1 ] =
в€љ
2. By Proposition 11.16, Ki = Kiв€’1 ( Оіiв€’1 ) for Оіiв€’1 в€€ Kiв€’1 , and since Ki is
real, Оіiв€’1 > 0. Therefore, by repeated application of Proposition 13.3, it can be
shown that every element of Kn is constructible.
Conversely, suppose that О± в€€ K; thus О± appears as the coordinate of a point
constructible from (0, 0) and (1, 0) by a п¬Ѓnite number of the operations 1 to 5
preceding Theorem 13.1. We prove the result by induction on m, the number of
constructible numbers used in reaching О±.
Suppose that Xk = {x1 , . . . , xk } is a set of numbers that have already been
constructed, that is, have appeared as coordinates of constructible points. When
the next number xk+1 is constructed, we show that [Q(Xk+1 ) : Q(Xk )] = 1 or 2,
where Q(Xk+1 ) = Q(x1 , . . . , xk , xk+1 ).
We п¬Ѓrst show that if we perform either operation 1 or 2 using previously
constructed numbers in Xk , the coefп¬Ѓcients in the equation of the line or circle
remain in Q(Xk ). If we perform operation 3, the newly constructed numbers
remain in Q(Xk ), and if we perform operation 4 or 5, the newly constructed
numbers are either in Q(Xk ) or an extension п¬Ѓeld of degree 2 over Q(Xk ).
Operation 1. The line through (О±1 , ОІ1 ) and (О±2 , ОІ2 ) is (y в€’ ОІ1 )/(ОІ2 в€’ ОІ1 ) =
(x в€’ О±1 )/(О±2 в€’ О±1 ), and if О±1 , О±2 , ОІ1 , ОІ2 в€€ Xk , the coefп¬Ѓcients in the equation
of this line lie in Q(Xk ).
CONSTRUCTIBLE NUMBERS 255

Operation 2. The circle with center (О±1 , ОІ1 ) and radius equal to the distance from
(О±2 , ОІ2 ) to (О±3 , ОІ3 ) is (x в€’ О±1 )2 + (y в€’ ОІ1 )2 = (О±2 в€’ О±3 )2 + (ОІ2 в€’ ОІ3 )2 , and all
the coefп¬Ѓcients in this equation lie in Q(Xk ).
Operation 3. Let О±ij , ОІj в€€ Q(Xk ). Then the lines

О±11 x + О±12 y = ОІ1
О±21 x + О±22 y = ОІ2

meet in the point (x, y), where using CramerвЂ™s rule,

ОІ1 О±12 О±11 О±12
x = det det
ОІ2 О±22 О±21 О±22

and
О±11 ОІ1 О±11 О±12
y = det det
О±21 ОІ2 О±21 О±22

as long as they are not parallel. Both of these coordinates are in Q(Xk ).
Operation 4. To obtain the points of intersection of a circle and line with coef-
п¬Ѓcients in Q(Xk ), we eliminate y from the equations to obtain an equation of
the form
О±x 2 + ОІx + Оі = 0 where О±, ОІ, Оі в€€ Q(Xk ).

The line and circle intersect if ОІ 2 в€’ 4О±Оі 0 and the x coordinates of
в€’ОІ В± ОІ 2 в€’ 4О±Оі
the intersection points are x = , which are in Q(Xk ) or
2О±
Q(Xk )( ОІ 2 в€’ 4О±Оі ). Similarly, the y coordinates are in Q(Xk ) or in an extension
п¬Ѓeld of degree 2 over Q(Xk ).
Operation 5. The intersection of the two circles

x 2 + y 2 + О±1 x + ОІ1 y + Оі1 = 0
x 2 + y 2 + О±2 x + ОІ2 y + Оі2 = 0

is the same as the intersection of one of them with the line

(О±1 в€’ О±2 )x + (ОІ1 в€’ ОІ2 )y + (Оі1 в€’ Оі2 ) = 0.

This is now the same situation as in operation (4).
Initially, m = 2, X2 = {0, 1}, and Q(X2 ) = Q. It follows by induction on m,
the number of constructible points used, that

О± в€€ Q(Xm ) вЉ‡ Q(Xmв€’1 ) вЉ‡ В· В· В· вЉ‡ Q(X3 ) вЉ‡ Q(X2 ) = Q,
256 13 GEOMETRICAL CONSTRUCTIONS

where [Q(Xk+1 ) : Q(Xk )] = 1 or 2 for 2 k m в€’ 1. Furthermore, each exten-
sion п¬Ѓeld Q(Xk ) is a subп¬Ѓeld of R because Q and Xk are sets of real numbers. By
dropping each п¬Ѓeld Q(Xi ) that is a trivial extension of Q(Xiв€’1 ), it follows that

О± в€€ Kn вЉ‡ Knв€’1 вЉ‡ В· В· В· вЉ‡ K0 = Q

where [Ki : Kiв€’1 ] = 2 for 1 i n.

Corollary 13.6. If О± is constructible, then [Q(О±) : Q] = 2r for some r 0.

Proof. If О± is constructible, then О± в€€ Kn вЉ‡ Knв€’1 вЉ‡ В· В· В· вЉ‡ K0 = Q, where Ki
is an extension п¬Ѓeld of degree 2 over Kiв€’1 . By Theorem 11.6,

[Kn : Q(О±)][Q(О±) : Q] = [Kn : Q]
= [Kn : Knв€’1 ][Knв€’1 : Knв€’2 ] В· В· В· [K1 : Q] = 2n .

Hence [Q(О±) : Q]|2n ; thus [Q(О±) : Q] = 2r for some r 0.

Corollary 13.7. If [Q(О±) : Q] = 2r for some r 0, then О± is not constructible.

Corollary 13.6 does not give a sufп¬Ѓcient condition for О± to be constructible,
as shown in Example 13.17 below.

Example 13.8. Can a root of the polynomial x 5 + 4x + 2 be constructed using
straightedge and compass?

Solution. Let О± be a root of x 5 + 4x + 2. By EisensteinвЂ™s criterion, x 5 + 4x +
2 is irreducible over Q; thus, by Corollary 11.12, [Q(О±) : Q] = 5. Since 5 is not
a power of 2, it follows from Corollary 13.7 that О± is not constructible.

Example 13.9. Can a root of the polynomial x 4 в€’ 3x 2 + 1 be constructed using
straightedge and compass?
в€љ
Solution. Solving the equation x 4 в€’ 3x 2 + 1 = 0, we obtain x 2 = (3 В± 5)/2
в€љ
and x = В± (3 В± 5)/2. It follows from Theorem 13.5 that all these roots can
be constructed.

DUPLICATING A CUBE

Let l be the length of the sides of a given cube soв€љ its volume is l 3 . A cube
that
3
with double the volume will have sides of length 2 l.
в€љ
3
Proposition 13.10. 2 is not constructible.
TRISECTING AN ANGLE 257

в€љ
Proof. 3 2 is a root of x 3 в€’ 2 which, by the rational roots theorem (Theo-
в€љ
rem 9.25), is irreducible over Q. Hence, by Corollary 11.12, [Q( 3 2) : Q] = 3
в€љ
so, by Corollary 13.7, 3 2 is not constructible.
в€љ
Since we cannot construct a length of 3 2 l starting with a length l, the ancient
problem of duplicating the cube is insoluble.

TRISECTING AN ANGLE

Certain angles can be trisected using straightedge and compass. For example,
ПЂ, ПЂ/2, 3ПЂ/4 can be trisected because ПЂ/3, ПЂ/6, and ПЂ/4 can be constructed.
However, we show that not all angles are trisectable by proving that ПЂ/3 cannot
be trisected.
If we are given the angle П†, we can drop a perpendicular from a point a
unit distance from the angle to construct the lengths cos П† and sin П†, as shown
in Figure 13.4. Conversely, if either cos П† or sin П† is constructible, it is pos-
sible to construct the angle П†. Hence, if we are given an angle П†, we can
construct all numbers in the extension п¬Ѓeld Q(cos П†). Of course, if cos П† в€€ Q,
then Q(cos П†) = Q.
We can now consider those numbers that are constructible from Q(cos П†). This
notion of constructibility is similar to our previous notion, and similar results
hold, except that the starting п¬Ѓeld is Q(cos П†) instead of Q.

Theorem 13.11. The angle П† can be trisected if and only if the polynomial
4x 3 в€’ 3x в€’ cos П† is reducible over Q(cos П†).

Proof. Let Оё = П†/3. The angle Оё can be constructed from П† if and only if
cos Оё can be constructed from cos П†. It follows from De MoivreвЂ™s theorem and
the binomial theorem that

cos П† = cos 3Оё = 4 cos3 Оё в€’ 3 cos Оё.

Hence cos Оё is a root of f (x) = 4x 3 в€’ 3x в€’ cos П†.
If f (x) is reducible over Q(cos П†), then cos Оё is a root of a polynomial of
degree 1 or 2 over Q(cos П†); thus [Q(cos П†, cos Оё ) : Q(cos П†)] = 1 or 2. Hence,
by Propositions 11.16 and 13.3, cos Оё is constructible from Q(cos П†).

1
sin f
f
cos f

Figure 13.4. Constructing sin П† and cos П† from the angle П†.
258 13 GEOMETRICAL CONSTRUCTIONS

If f (x) is irreducible over Q(cos П†), then [Q(cos П†, cos Оё ) : Q(cos П†)] = 3,
and it follows, by a proof similar to that of Theorem 13.5, that cos Оё cannot be
constructed from Q(cos П†) by using straightedge and compass.

Corollary 13.12. If cos П† в€€ Q, then the angle П† can be trisected if and only if
4x 3 в€’ 3x в€’ cos П† is reducible over Q.

For example, if П† = ПЂ/2, then П† can be trisected because the polynomial
4x в€’ 3x + 0 is reducible over Q.
3

Proposition 13.13. ПЂ/3 cannot be trisected by straightedge and compass.

Proof. The polynomial f (x) = 4x 3 в€’ 3x в€’ cos(ПЂ/3) = 4x 3 в€’ 3x в€’ 1 . Now,
2
by the rational roots theorem (Theorem 9.25), the only possible roots of 2f (x) =
8x 3 в€’ 6x в€’ 1 are В±1, В± 1 , В± 1 , or В± 1 . We see from the graph of f (x) in Fig-
2 4 8
ure 13.5 that none of these are roots, except possibly в€’ 1 or в€’ 1 . However,
4 8
f (в€’ 1 ) = 16 and f (в€’ 1 ) = в€’ 128 ; thus f (x) has no rational roots. Hence f (x) is
3 17
4 8
irreducible over Q, and by Corollary 13.12, ПЂ/3 cannot be trisected by straight-
edge and compass.

Example 13.14. Archimedes showed that, if we are allowed to mark our straight-
edge, it is possible to trisect any angle.
Construction. Let AOB be the angle П† we are to trisect. Draw a circle with
center O and any radius r and let this circle meet OA and OB in P and Q. Mark
two points X and Y on our straightedge of distance r apart. Now move this
straightedge through Q, keeping X on OA until Y lies on the circle, as shown
in Figure 13.6. Then we claim that the angle OXY is П†/3, and hence the angle
AOB is trisected.
Solution. Let angle OXY = Оё . Since triangle XYO is isosceles, the angle XOY =
Оё . Now
angle OYQ = angle OXY + angle XOY = 2Оё.

f(x)

0
в€’1 x
1

в€’1

Graph of f (x) = 4x 3 в€’ 3x в€’ 1 .
Figure 13.5. 2
CONSTRUCTING REGULAR POLYGONS 259

B

2q Q
Y
2q
r
f
X q q
r P A
O

Figure 13.6. Trisection of the angle П† using a marked ruler.

Triangle YOQ is isosceles, so angle OQY = 2Оё . Also,

П† = angle AOB = angle OXQ + angle OQX = Оё + 2Оё = 3Оё.

Hence Оё = П†/3.

SQUARING THE CIRCLE

Given any circle of radius r, its area is ПЂr 2 , so that a square with theв€љsame
в€љ
area has sides of length ПЂ r. We can square the circle if and only if ПЂ is
constructible.
в€љ в€љ
Proposition 13.15. [Q( ПЂ) : Q] is inп¬Ѓnite, and hence ПЂ is not constructible.

Proof. The proof of this depends on the fact that ПЂ is transcendental over
Q; that is, ПЂ does not satisfy any polynomial equation with rational coefп¬Ѓcients.
This was mentioned in Chapter 11, and a proof is given in Stewart .
в€љ в€љ в€љ
Q(ПЂ ) is a subп¬Ѓeld of Q( ПЂ ) because ПЂ = ( ПЂ )2 в€€ Q( ПЂ). Since ПЂ is tran-
scendental, ПЂ, ПЂ 2 , ПЂ 3 , . . . are linearly independent over Q, and [Q(ПЂ) : Q] is
inп¬Ѓnite. Therefore,
в€љ в€љ
[Q( ПЂ) : Q] = [Q( ПЂ) : Q(ПЂ )][Q(ПЂ) : Q]
в€љ
is also inп¬Ѓnite. Hence, by Corollary 13.7, ПЂ is not constructible.

Hence the circle cannot be squared by straightedge and compass.

CONSTRUCTING REGULAR POLYGONS

Another problem that has been of great interest to mathematicians from the time
of the ancient Greeks is that of constructing a regular n-gon, that is, a regular
polygon with n sides. This is equivalent to constructing the angle 2ПЂ/n or the
260 13 GEOMETRICAL CONSTRUCTIONS

number cos(2ПЂ/n). The Greeks knew how to construct regular polygons with
three, four, п¬Ѓve, and six sides, but were unable to construct a regular 7-gon.
It is well known how to construct an equilateral triangle and a square using
straightedge and compass. We proved in Example 11.15 that cos(2ПЂ/5) =
в€љ
( 5 в€’ 1)/4; thus a regular pentagon can be constructed. Furthermore, if a regu-
lar n-gon is constructible, so is a regular 2n-gon, because angles can be bisected
using straightedge and compass. Proposition 13.13 shows that ПЂ/9 cannot be
constructed; hence 2ПЂ/9 and a regular 9-gon cannot be constructed.
In 1796, at the age of 19, Gauss discovered that a regular 17-gon could be
constructed and later showed the only regular n-gons that are constructible are the
ones for which n = 2k p1 В· В· В· pr , where k 0 and p1 , . . . , pr are distinct primes
m m
of the form 22 + 1. Prime numbers of the form 22 + 1 are called Fermat
primes. Pierre de Fermat (1601вЂ“1665) conjectured that all numbers of the form
m
22 + 1 are prime. When m = 0, 1, 2, 3, and 4, the numbers are 3, 5, 17, 257, and
65,537, respectively, and they are all prime. However, in 1732, Euler discovered
5
 << стр. 10(всего 13)СОДЕРЖАНИЕ >>