Given an integer n > 2, let Vn be the set of integers 1 + kn for k a positive integer. A number m in Vn is called indecomposable if it cannot be expressed as the product of two members of Vn. Prove that there is a number in Vn which can be expressed as the product of indecomposable members of Vn 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 Vn. But a little care is needed, since this is not necessarily true.
Try taking a = b = n - 1, c = d = 2n -1. a2 must be indecomposable because it is less than the square of the smallest element in Vn. If ac = 2n2 - 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 c2 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