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

[40] 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

3’ ad c b

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

addition table of GF(n). Then

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

Subject bcd adc dab cba

B

Group cdb dca abd bac

C

dbc cad bda acb

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 [40] 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 [40].)

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 [39] 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 [40] 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

copyright holder. Readers are kindly

requested to refer to the printed version

of this article.

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. [38] and Laywine and Mullen [40] 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 [35].

√ √ √

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