A History of Mathematics From Mesopotamia to Modernity

258 A History ofMathematics

Solutions to exercises

These are perhaps unduly hard, but it is almost impossible to find easier ones; and of course, no
exercises have been included on Fermat...

1. (a) If(mn)p=m(n

p)

, thenmnp=m(n

p)

. This means that eitherm=1 (since then all powers
ofmare the same) ornp=npandmis arbitrary; equivalently,np−^1 =p. This is possible (1) if
p=1,narbitrary; or (2) ifn=p=2.
(b) Finding a system of generators is easy; inductively, one chooses anya 1 .Ifa 1 ,...,ai− 1
have been chosen and do not generate the group, one chooses someaiinGbut not in the
subgroup generated bya 1 ,...,ai− 1. SinceGis finite, eventually the process ends.
From the characterization of the generators, one deduces that the productsai 1 ,...aikwith
i 1 <i 2 <···<ikare all different. There are 2mof these, so 2m≤n. And any automorphismf
ofGis determined byf(a 1 ),...,f(am). Since there are at mostnpossibilities for each of these,
the number of automorphisms is≤nm. Now usingmlog 2≤logn,m≤logn/log 2, which
proves it.
2. (a) The tape must of course not only contain the figures, but a symbol to tell the machine
where the number stops; it must therefore read something like ‘x1011’, where ‘x’ means ‘stop
here’ (otherwise the machine would have to move on in case of finding other figures!) At the
start, the machine is at the rightmost position, and it reads and writes moving left. We can
characterize the states as: S (start), N (not carrying), C (carrying), and F (finish). Rules are:

1. If state is S and symbol read is 0, change state to N, change symbol to 1, move left. If symbol
   read is 1, change state to C, change symbol to 0, move left.


2. If state is N and symbol read is 0 or 1, move left and do not change state or symbol. If
   symbol read is x, change state to F, do not change symbol, stop.


3. If state is C and symbol read is 0, change state to N, change symbol to 1, move left. If symbol
   read is 1, change symbol to 0 and do not change state, move left.


4. If state is C and symbol read is x, change symbol to 1, move left, write x, change state to
   F, stop.
   (b) The programme computes the sequence:
   x 0 =1;xn= 1 +( 1 /xn− 1 ). these are (the computer’s approximations to) the successive
   steps in the continued fraction

1 +

1

1 +( 1 / 1 +···)

This is the solution ofx= 1 +( 1 /x),or( 1 +

√

5 )/2. How accurate the answer is depends on

the number of places stored in the computer by the particular programme you are using. What

is printed is the 100th approximation, which will probably be quite close. (In one version which

I used, after about 25 steps the programme did not fix, but got into a two-cycle:a,b,a,b,...

whereaandbdiffered in the last decimal point. This illustrates the way in which the finiteness

of computers affects the result.)

3. (a)f^2 (z)=z^4 ,f^3 (z)=z^8 , and in generalfn(z)=z(^2

n)

. Hence,fn(z)=zifz(^2

n)

=z. Discount

z=0 (we are on the circle), and we are left withz(^2

n− 1 )

=1;zisa(2n−1)th root of 1,

exp( 2 kπ/( 2 n− 1 )).