Exercises 41

5n7d13

↓

(AB)dJ

2d3d5n−d11

↓ (EF

)dK

2d5n−d7d13

↓

(AB)dJ

22d3d5n−2d11

↓ (EF

)dK

22d5n−2d7d13

↓

(AB)dJ

.

.

.

↓ (EF

)dK

2qd5r7d13

↓

(AB)rA

2n3r7d−r−117

(if r 0) C I (if r = 0)

2n3r−17d−r−119 2n7d−1

↓

(DG)nH

↓

LnM d−1N

3r−15n7d−r11 3n5n+111

↓ (EF

)r−1K

↓ (EF

)nK

5n7d−113 5n+17n13

Figure 4. The action of Conway’s prime-producing machine when

started with

5n7d13,

where 0 d n. The variables q and d are

defined by the division algorithm: n = dq + r where 0 ≤ r d.

every pair a, b ∈ S and every odd prime p. We make this assumption

from now on.

(c) Now argue that v2(a) = v2(b) for every pair of elements a, b ∈ S.

Thus, dividing through by a suitable power of 2, we may (and do)

assume that all the elements of S are odd.

(d) Finally, show that for each pair of elements a, b ∈ S, we have

a + b =

2v2(a+b)

p2

pmin{vp(a),vp(b)}.

Show that this equation leads to a contradiction if a and b are

chosen to be congruent modulo 4.

24. Figure 4, based on Conway’s article [Con87], describes the action of

Conway’s prime-producing machine. Decipher this figure and explain

how it proves Theorem 1.8. For a more detailed explanation of the

workings of Conway’s prime-producing machine, see Guy’s expository

article [Guy83].