Given an integer n > 2, let V_{n} be the set of integers 1 + kn for k a positive integer. A number m in V_{n} is called indecomposable if it cannot be expressed as the product of two members of V_{n}. Prove that there is a number in V_{n} which can be expressed as the product of indecomposable members of V_{n} in more than one way (decompositions which differ solely in the order of factors are not regarded as different).

**Solution**

Take a, b, c, d = -1 (mod n). The idea is to take abcd which factorizes as ab.cd or ac.bd. The hope is that ab, cd, ac, bd will not factorize in V_{n}. But a little care is needed, since this is not necessarily true.

Try taking a = b = n - 1, c = d = 2n -1. a^{2} must be indecomposable because it is less than the square of the smallest element in V_{n}. If ac = 2n^{2} - 3n + 1 is decomposable, then we have kk'n + k + k' = 2n - 3 for some k, k' >= 1. But neither of k or k' can be 2 or more, because then the lhs is too big, and k = k' = 1 does not work unless n = 5. Similarly, if c^{2} is decomposable, then we have kk'n + k + k' = 4n - 4. k = k' = 1 only works for n = 2, but we are told n > 2. k = 1, k' = 2 does not work (it would require n = 7/2). k = 1, k' = 3 only works for n = 8. Other possibilities make the lhs too big.

So if n is not 5 or 8, then we can take the number to be (n - 1)^{2}(2n - 1)^{2}, which factors as (n - 1)^{2} x (2n - 1)^{2} or as (n - 1)(2n - 1) x (n - 1)(2n - 1). This does not work for 5 or 8: 16·81 = 36·36, but 36 decomposes as 6·6; 49·225 = 105·105, but 225 decomposes as 9·25.

For n = 5, we can use 3136 = 16·196 = 56·56. For n = 8, we can use 25921 = 49·529 = 161·161.

Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

© John Scholes

jscholes@kalva.demon.co.uk

12 Oct 1998