Show that for each $n \ge 2$, there is a set $S$ of $n$ integers such that $(a-b)^2$ divides $ab$ for every distinct $a, b\in S$.
Problem
Source:
Tags: induction, number theory, least common multiple
22.09.2007 20:59
Lemma 1 If $ \gcd(a,b) = m$ and $ a = mk, b = ml$, then $ (a-b)^{2}|ab$ iff $ k-l = 1$. Proof $ (a-b)^{2}= m^{2}(k-l)^{2}$; $ ab = m^{2}kl$ so $ (a-b)^{2}|ab\Leftrightarrow (k-l)^{2}|kl$. But because$ \gcd(a,b) = m$and$ a = mk, b = ml$,$ \gcd(k,l) = 1$and if $ k-l = q > 1$ then $ k-l$ is divisible by a prime$ p\geq 2$, and then$ p$divides$ k$or$ l$, wolog$ p|k$, but then as $ p|(k-l)$ then $ p|l$ which contradicts the fact that $ \gcd(k,l) = 1$. So,$ k-l = 1$and the lemma is proved in one direction. Now, $ (a-b)^{2}= (mk-ml)^{2}= m^{2}(k-l)^{2}= m^{2}|m^{2}kl = (mk)(ml) = ab$ so $ (a-b)^{2}|ab$ and the lemma is proved in the other direction. Lemma 2 If $ x,y$ are two distinct positive integers with $ x > y$ such that $ (x-y)^{2}|xy$ then for any positive integer $ c\geq 2$, the numbers $ t = c^{x}-1, s = c^{x-y}(c^{y}-1)$ then $ (s-t)^{2}|st$. Proof By lemma 1, if $ \gcd(x,y) = m$ and $ x = mk,y = ml$ then $ k-l = 1$. Then, $ t = c^{x}-1 = c^{mk}-1 = (c^{m}-1)(c^{(k-1)m}+c^{(k-2)m}+...+c^{m}+1)$ Also, $ s = c^{x-y}(c^{y}-1) = c^{mk-ml}(c^{ml}-1) = c^{m(k-l)}(c^{m}-1)(c^{(l-1)m}+c^{(l-2)m}+...+c^{m}+1)$ $ = (c^{m}-1)(c^{m}(c^{(l-1)m}+c^{(l-2)m}+...+c^{m}+1)) = (c^{m}-1)((c^{lm}+c^{(l-1)m}+...+c^{2m}+c^{m}))$ $ = (c^{m}-1)(c^{(k-1)m}+c^{(k-2)m}+...+c^{m})$ because $ k-l = 1$. Therefore, because we can find numbers $ d = c^{m}-1, e = c^{(k-1)m}+c^{(k-2)m}+...+c^{m}+1, f = c^{(k-1)m}+c^{(k-2)m}+...+c^{m}$ such that $ t = de, s = df, e-f = 1$ then by lemma 1 $ (s-t)^{2}|st$ and lemma 2 is proved. Finally note that for the numbers $ c^{z}= c^{z-u}(c^{u})$ and $ c^{z-u}(c^{u}-1)$ where $ c$ is a positive integer greater than $ 1$ there exist numbers $ d = c^{z-u}, e = c^{u}, f = c^{u}-1$ such that $ c^{z}= de, c^{z-u}(c^{u}-1) = df, e-f = 1$ then by lemma 1 $ (c^{z}-c^{z-u}(c^{u}-1))^{2}|(c^{z}*c^{z-u}(c^{u}-1))$ -- call this property lemma 3. Now, we can construct the set $ S$ inductively. Start with numbers $ 1,2$ as the base step for $ n = 2$. Then, when we have $ k$ numbers $ a_{1}< a_{2}< ... < a_{k}$ belonging to set $ S$ and satisfying the conditions, we can construct a new set of $ k+1$ numbers: $ b_{1}< b_{2}< ...b_{k+1}$ where for $ i = 1,2,...,k$, $ b_{i}= r^{a_{k}-a_{i}}(r^{a_{i}}-1)$ and $ b_{k+1}= a^{k}$ where $ r$ is any positive integer greater than $ 1$. Then, for any $ i,j\in\{1,2,...,k\}$, $ i < j$ by lemma 1, $ (b_{j}-b_{i})^{2}|b_{i}b_{j}$, and for any $ i\in\{1,2,...,k\}$, by lemma 3, $ (b_{k+1}-b_{i})^{2}|b_{k+1}b_{i}$ so the constructed set of $ k+1$ numbers satisfies the conditions of the problem. Then, from the new set with $ k+1$ numbers we can construct a set with $ k+2$ numbers and so on, until we reach $ n$, and the result follows.
26.10.2007 17:03
I have am other method . Lemma 1 $ A = \{a\}$ and $ |A| = k$ satisfy $ (a - b)^2|ab,\forall a,b\in A$ then the set $ A_1 = \{a + d\}$ has this property where $ \prod_{i > j = 1}^k (a_i - a_j)^2|d$ satisfy. Lemma 2 If the set $ A$ satisfy the condition then the set $ A + \{0\}$ also satisfy the condition. It is quite easy to prove . Now we prove by induction: $ k = 2$ then chose $ a,b = 1,2$ Suppose it is true for $ k$ we prove it is also true for $ k + 1$ From lemma 1,lemma 2 then it true . With this method we can solve problem. Let $ a,b\in N$ satisfy condition $ (a - b)^2|ab$ then exist A a set such that 1)$ a,b\in A$ 2)$ (x - y)^2|xy,\forall x,y\in A$
01.02.2011 23:54
Assume the set is finite. Let B be the lcm of every element in the set. Add 0 to the set. Increase each element by B. We now have a larger set so there is no maximum and the set can be infinite. edit: So we can make a set of any finite size. Luckily this is all the problem was asking for and we dont need it to be an infinite set.
02.02.2011 03:12
We must be careful! As stated above, "We now have a larger set so there is no maximum and the set can be infinite.", this was yet unproven, and, moreover, false, as I will show below. All that was proven is that from a set with $n$ elements we can create one with $n+1$ elements, and so we can create as large a set as wanted, but not necessarily an infinite set. Consider any such set $S$. Take an element $a \in S$, $a \neq 0$. Then for all elements $b\in S$, $b \neq a$, we will need have $(a-b)^2 \mid ab$, hence $(a-b)^2 \leq |ab|$, therefore $b^2 \leq |ab| + 2ab - a^2 < 3|ab|$. So, $|b| < 3|a|$, therefore $|S| \leq 6|a|$.