mathschallenge.net

Problem

A positive integer, N, is an sum-product number if there exists a set of positive integers:
S = {a₁,a₂,...,a_k}, such that N = a₁ a₂ ... a_k = a₁ + a₂ + ... + a_k. 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 1p, hence N cannot be prime.

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

N = ab = (a1)ba+a+b.

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

As a,b 2, let a=2 (the minimum value), so m = (a1)ba b2 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 = 25 = 10, and as 2+5=7, we can write,
10 = 25111 = 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.