Given positive integer n, consider the set of numbers {n²+1, n²+2, ... (n+1)²}. If we pick two numbers x and y out of that set, how many different values can the product xy take?
(In reply to
re: what am I missing? by owl)
I think owl put his/her finger on the problem, that being 'how do we know each pair produces a unique product?'. This i will attempt to prove:
Consider the case where we have two distinct pairs of numbers (a,b) and (c,d) from the set with the same product. It follows that to be distinct, these pairs must be mutually exclusive (ie. a != c or d, and b != c or d).
Let x = gcd(a,c), y = gcd(b,d), then there must be integers i and j such that a = ix, b = jy, c = jx, d = iy. Further, since a != c or d, it follows that i != j, and x != y. WOLOG let i < j, and x < y.
Since ix > n2, it follows that i + x > 2n. Since j >= i + 1, y >= x + 1, we know
- b = jy
- b >= (i+1)(x+1)
- b >= ix + (i + x) + 1
- b > n2 + 2n + 1
- b > (n+1)2, a contradiction.
Therefore, there are no two pairs of numbers in the set with the same product, and owl's upper bound of n(2n+1) is always the total number of distinct products. (corrected after subsequent posts, thanks guys)
Edited on August 16, 2005, 11:30 pm
re(2): what am I missing?
