(if r 0) C I (if r = 0)
Figure 4. The action of Conway’s prime-producing machine when
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 =
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