<<

. 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
[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

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

<<

. 10
( 13)



>>