 Sum Product Numbers

Problem

A positive integer, N, is an sum-product number if there exists a set of positive integers:
S = {a1,a2,...,ak}, such that N = a1 a2 ... ak = a1 + a2 + ... + ak. In order for the set to be a sum and product, it is necessary that S contains at least two elements.

Prove that N is a sum-product number iff it is composite.

Solution

If N is prime, the two factors must be 1 and p. However, 1+p 1 p, hence N cannot be prime.

If N is composite it can be written as N = ab, where a,b 2.

N = ab = (a 1)b a+a+b.

Let m = (a 1)b a, so that N = ab = m+a+b.

As a,b 2, let a=2 (the minimum value), so m = (a 1)b a b 2 0.

As N = ab = m+a+b, and m is never negative, we demonstrate that the sum will be equal to or less than the product.

In which case, the difference, m, can be made up of a sum of ones, for which adding as many ones as necessary will not affect the product.

For example, N = 10 = 2 5 = 10, and as 2+5=7, we can write,
10 = 2 5 1 1 1 = 2+5+1+1+1.

Thus N is a sum-product number iff it is composite.

If each element of S can be any integer (positive or negative), prove that all positive integers are sum-product numbers.

Problem ID: 200 (10 Jan 2005)     Difficulty: 3 Star

Only Show Problem