Skip to main content.

Solution to puzzle 127: Prime number generator

Skip restatement of puzzle.Let P = {p1, ... , pn} be the set of the first n prime numbers.  Let S be an arbitrary (possibly empty) subset of P.  Let A be the product of the elements of S, and B the product of the elements of S', the complement of S.  (An empty product is assigned the value of 1.)

Prove that each of A + B and |A − B| is prime, provided that it is less than pn+12 and greater than 1.


Firstly, by the Fundamental Theorem of Arithmetic, each of p1, ... , pn divides one of A, B, but not the other.
Hence none of p1, ... , pn divides A + B or |A − B|.
Therefore, if |A − B| > 1 (we always have A + B > 1), any prime divisor of A + B or |A − B| must be greater than or equal to pn+1.
Further, there can only be one such prime divisor, as we have stipulated that A + B and |A − B| are less than pn+12.

Therefore, each of A + B and |A − B| is prime, provided that it is less than pn+12 and greater than 1.

Source: More Mathematical Morsels (Morsel 20), by Ross Honsberger

Back to top