8
$\begingroup$

Prove that for every natural number $n$, there is a set $S$ of $n$ natural numbers such that for any two different numbers $a,b$ From $S$ the number $a-b$ divides $a$ and $b$ and no another number from the group S.

I tried lots of directions. I've been trying to use the Chinese remainder theorem, Euclid's algorithm and I think I have a direction. I will write it down, but anyways if anyone solves another way I would love to hear his/her solution.

I will solve for a case where n = 3, but the idea is the same idea for any other n.
Let's start by taking a multiple of 3 different prime numbers, say, $3,5,7$. Now let's say $m = 3 * 5 * 7$. The first number will be $m / 3 = 35$. The second would be $m / 5 = 21$. And the third would be $m / 7 = 15$. Let's take the first and second and execute Euclid's algorithm on them and get their gcd, we will solve for the inverse and get: $7 = 2 * 21-35$. We will replace the first and second numbers with $35 * 1 = 35$ and $21 * 2 = 42$. Now let's do the same on the first and third and we get: $5 = 1 * 35-2 * 15$. We will replace the third with $2 * 15 = 30$ and the first one will remain the same. We will also perform this action on the second and third and we will get $84$ and $90$.Then, we multiply the last ($35$) by $90/30=3$ and we will be lucky to get ($105,90,84$) three numbers that work. Obviously this method does not work in the general case (when we replace the numbers we also change their difference with others and maybe even make them divisible by other differences) but this method gives direction and intuition to the question.

$\endgroup$
  • $\begingroup$ This is unhelpful, but, for n=3, your numbers are 6 times 14, 6 times 15, and then 7 times 15. Not sure if this pattern extends. $\endgroup$ – barrycarter Sep 30 at 16:23
3
$\begingroup$

Try spamming CRT, that is what I would say.

The general way to understand this question is to start with small $n$, start constructing the set, and you gain experience when you fail. After a few failure you should see that making $a-b$ divide both $a$ and $b$ is the easier part, while $a-b$ cannot divide by other elements (let's call it the "exclusive divisibility condition") is the bottleneck.

For brevity I will write down a construction for $n = 5$, but I think you can easily extend it to the general case. Let the set to be constructed called $$\{s_1 = x, s_2 = x+a, s_3 = x+a+b, s_4 = x+a+b+c, s_5 = x+a+b+c+d\}.$$

To satisfy the "exclusive divisibility condition", the heuristics is to make all the differences $$a,b,c,d,a+b,b+c,c+d,a+b+c,b+c+d,a+b+c+d$$ "as pairwise relatively prime as possible". It is impossible to make it perfectly pairwise relatively prime (if you doubt it, you try it). The problem when $n=5$ will be at modulo $2^k$ and $3^k$.

To handle this, we make the following restrictions: $$ \begin{aligned} &a \equiv 2^3 \pmod{2^3}, &a \equiv 3^3 \pmod{3^3};\\ &b \equiv 2^2 \pmod{2^3}, &b \equiv 3^2 \pmod{3^3};\\ &c \equiv 2^1 \pmod{2^3}, &c \equiv 3^1 \pmod{3^3};\\ &d \equiv 2^0 \pmod{2^3}, &d \equiv 3^0 \pmod{3^3}. \end{aligned} $$

This is all prevents the differences to be not pairwise relatively prime. Let $P$ be the set of primes between $5$ and $\binom52$. For any $p \in P$, we also request $$ a \equiv 0 \pmod p, \quad b,c,d \equiv 1 \pmod p. $$

Next we construct $a$. We find $a$ satisfying the restrictions modulo $2^3$, $3^3$, and $P$. The existence is guaranteed by CRT.

Then we construct $b$. Let $D_1$ be the set of prime divisors of $a$. For all $p \in D_1$, we need $b \not\equiv 0 \pmod p$, $b+a \not\equiv 0 \pmod p$, together with the aforementioned restrictions modulo $2^3$, $3^3$, and $P$. The existence is again guaranteed by CRT.

For $c$, we do similar things. $D_2$ be the union of set of prime divisors of $a$, $b$, and $a+b$. we need $c \not\equiv 0 \pmod p$, $c+b \not\equiv 0 \pmod p$, $c+b+a \not\equiv 0 \pmod p$, together with the aforementioned restrictions modulo $2^3$, $3^3$, and $P$. The existence is again guaranteed by CRT.

Do the same for $d$. Let $D$ be the union of the set of prime divisors among all the differences. For $2$ and $3$, you need $x \equiv 0 \pmod{2^33^3}$. For other prime $p \in D$, you decide $x \pmod p$ according to where $p$ came from. For instance, if $p \ | \ b+c$, then you need $x+a \equiv x+a+b+c \equiv 0 \pmod p$. The existence of $x$ is by CRT.

You have to prove that the set we construct is legit. The divisibility condition follows from the construction, and the "exclusive divisibility" is true since all the differences contains a unique prime divisor, and that prime divisor is only divisible by two elements in the set, guaranteed by this construction.

$\endgroup$
1
$\begingroup$

Fix $M$ with $M>n^3$ and perform the following algorithm:

Suppose $2\le m<n$ and we have constructed $a_1<\ldots <a_m$ with the following property:

$P(m):$ The set $ D_m:=\{\,a_j-a_i\mid 1\le i<j\le m\,\}$ contains ${m\choose 2}$ integers $>M$, none of which is a multiple of another.

Then we can find $a_{m+1}$ such that $P(m+1)$ holds as follows: Each of the sets $a_i+d\Bbb Z$, $1\le i\le m$, $d\in D_m$ has density $<\frac 1M$. As there are less than $M$ such sets, the density of their union is $<1$, i.e., we can pick $a_{m+1}$ with $a_{m+1}>a_m+\max D_m$ and $a_{m+1}\notin \bigcup_{i,d}(a_i+d\Bbb Z)$. Then the $a_{m+1}-a_i$, $1\le i\le m$, are pairwise distinct, and are $>\max D_m$. Hence $D_{m+1}$ contains $m+1\choose 2$ integers $>M$. Assume $1\le i<j\le m+1$, $1\le i'<j'\le m+1$ and $a_j-a_i=c\cdot(a_{j'}-a_{i'})$ with some integer $c>1$.

  • If $j\le m$ and $j'\le m$, this contradicts $P(m)$
  • If $j'=m+1$ and $j\le m$, then $a_{j'}-a_{i'}>\max D_m\ge a_j-a_i$, contradiction
  • If $j'=j=m+1$, then $\frac{a_{j'}-a_{i'}}{a_j-a_i}\le \frac{a_{m+1}-a_1}{a_{m+1}-a_m}\le 1+\frac{a_m-a_1}{a_{m+1}-a_m}=1+\frac{\le \max D_m}{>\max D_m}<2$, contradiction
  • If $j=m+1$ and $j'\le m$, then $a_{m+1}=a_i+c\cdot (a_j-a_i)\in a_i+(a_j-a_i)\Bbb Z$, contradiction.

We conclude that no element of $D_{m+1}$ is a multiple of another element.

Thus by starting with $a_1=0$, $a_2=M+1$ (so that $P(2)$ holds), we finally find $a_1<\ldots <a_n$ such that $P(n)$ holds. Now let $A_i=\operatorname{lcm}\{\,|a_j-a_i|:j\ne i\,\}$. Then, because $a_j-a_i\mid A_i,A_j$ and hence $a_i\equiv a_j\pmod{\gcd(A_i,A_j)}$ for $1\le i<j\le n$, the Chinese Remainder Theorem guarantees a solution of the equations $$x+a_i\equiv 0\pmod{A_i}\qquad i=1,\ldots,n.$$ For such a solution, let $b_i=a_i+x$ (so that $A_i\mid b_i$) and $$S=\{\, b_i\mid 1\le i\le n\,\}.$$ This $S$ has the desired property: $b_j-b_i=a_j-a_i$ is a divisor of $A_i$ and $A_j$, hence also of $b_i$ and $b_j$. If it is also a divisor of $b_k$, then also of $b_k-b_i=a_k-a_i$. By $P(n)$, this is not possible unless $k=i$ or $k=j$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.