Five numbers whose difference is their gcd

Question

I have found $4$ numbers such that the positive difference of any two of them is their greatest common divisor. These numbers are $\{6,8,9,12\}$. I found them by trial and error. My question is, can we form a set of $5$ or more numbers with the same property? I'm having a really hard time finding them. If it's not possible, I am not sure how difficult it would be to prove that it's not possible so I don't want to embark on that blindly.

EDIT: I see that by programming we could try to find higher numbers by brute force. But what is the theory behind this? How can we prove or disprove that there exist arbitrarily large sets of numbers that satisfy this property?

Answer 1

This PARI/GP program searches the solutions by brute force. With limit $100$, we get following solutions.

? forvec(z=vector(5,j,[1,100]),gef=0;for(j=1,5,for(k=j+1,5,if(z[k]-z[j]<>gcd(z[j
],z[k]),gef=1)));if(gef==0,print(z)),2)
[36, 40, 42, 45, 48]
[40, 42, 44, 45, 48]
[40, 45, 48, 50, 60]
[60, 63, 64, 66, 72]
[60, 70, 72, 75, 80]
[60, 72, 75, 80, 90]
[72, 75, 76, 78, 80]
[72, 78, 80, 81, 84]
[72, 80, 81, 84, 90]
[72, 80, 84, 90, 96]
[80, 84, 88, 90, 96]
?

You can esily modify the program by replacing the $100$ by any higher number.

Answer 2

As previous comments show, yes. There are a few restrictions:

• The top number, can never be more than twice the bottom number(gcd(n,x) is never greater than n, so their difference can't be either).
• They must be coprime multiples of their difference, (if not, then the factor the multipliers have in common, goes unaccounted for.)
• There can't be more than 1 odd number, as 2 is in the difference of odd numbers, but neither number itself.
• There can't be more than the number of even divisors of the bottom number+1 (for even numbers)

Lets start with 100, then 200 is the highest the top number can be by item 1 . As 100 has divisors of 1,2,4,5,10,20,25,50, and 100 that's a start. 100=2*50,150=3*50 so 150 can work, so we now have $$\{100,150,200\}$$ 120 and 110 fail because 200 being in the mix as 80 resp. 90 doesn't divide either. But, if 200 leaves both work. 104 won't work with 110,120, or 150 so it fails. 102 fails with, 110,120,and 150, and all the odd numbers fail. But a highly composite number, might do better, as it has more divisors than any number less than it,and a lot can divide by the same thing.

720 to 1440 for example, 720 has 30 divisors:$$\{1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,30,36,40,45,48,60,72,80,90,120,144,180,240,360,720\}$$ 24 even divisors so maximum theoretical length will be length 25. 4 and 40 have difference 36 so they are paired as one or the other because 36 is a divisor of 720 not 724. Okay, there's too many differences that could be divisors.

Odd numbers could work well also though. It forces only 1 odd number, as all it's divisors are odd and odd+odd=even. 105,108,110,112,120 for example. This last case, is helped by factors in arithmetic progression I believe. This makes consecuitive multiples of the same difference possible. Prime factors ending in 1 and possibly 5 are a detriment to this method though, because unless the first addition of the factors lands on a multiple of 10 the two are incompatible.

A way to prove arbitrary length could be derived from arbitrarily long arithmetic progressions of certain types of end digits in prime factors of odd numbers.

Answer 3

After yesterday's adventures in brute force computation, I've settled down to do some theory.

There are in fact arbitrarily large sets of positive integers with the desired property. Below is a pseudocode algorithm that, given any such set, produces a larger one. I've not written out the justifications for the steps, but the verifications are routine except for Step 2, discussed below. The key observation is that the property is preserved if the set is translated by a common multiple of all the pairwise differences.

Algorithm

Input: A set of $t > 0$ positive integers $a_1,\ldots,a_t$ with $\operatorname{gcd}(a_i, a_j) = {\mid} a_i - a_j \mid$ for $i \ne j$.

Output: A set of $t + 1$ positive integers with the same property.

---

Step 1. (Initialize.)

Set $m = \operatorname{lcm}(\{a_i - a_j\})$ (the least common multiple of all the pairwise differences), $M = \operatorname{lcm}(\{a_i\})$.

Step 2. (Choose candidate for new entry.)

Find a positive integer $N$ such that the quotients $q_i := {\mid} N - a_i {\mid}/\operatorname{gcd}(N,a_i)$ are all coprime to $M$ and to each other.

Step 3. (Done?)

If all the $q_i = 1$, set $a_{t+1} := N$ and return $a_1,...,a_{t+1}$.

Step 4. (Deal with one $q_i$.)

If, for some $j$, $q_j \ne 1$, find a suitable multiple of $m$, say $km$, so that $q_j$ divides $a_j + km$ (and thus also $N + km$).

Set $a_i := a_i + km$ for each $i$, $N := N + km$, $m := \operatorname{lcm}(m, q_j)$.

Recompute the $q_i := {\mid} N - a_i {\mid}/\operatorname{gcd}(N,a_i)$.

Step 5. (Iterate.)

Go to step $3$.

---

In Step $2$ it is not obvious that such an $N$ must exist, so here is a formula: Let $N = M \operatorname{rad}(M)$, where $\operatorname{rad}(M)$ is the radical of $M$ (that is, the product of the distinct prime factors of $M$). This will work except in the trivial case $t = 1$, $a_1 = 1$, when $N = 2$ will do. In practice, this formula gives a very large $N$ and results in large values for the $q_i$, so searching for something smaller that also works is sensible.

Example

Start with $\{a_i\} = \{6, 8, 9, 12\}$.

We have $m = 24$, $M = 72$.

If we use $N = M \operatorname{rad}(M) = 432$, the $q_i$ are $71, 53, 47, 35$. As promised, they are pairwise coprime and also coprime to $72$.

For illustration, $N = 16$ is a more convenient choice; the $q_i$ are then $5, 1, 7, 1$.

To fix $q_1 = 5$, we need to find $k$ so that $5$ divides $24k + 6$. $k = 1$ will work. The new $a_i$ are $30, 32, 33, 36$; $N$ is now $40$; $m$ is now $120$; the $q_i$ are now $1, 1, 7, 1$.

Next we need to find $k$ so that $7$ divides $120k + 33$. $k = 2$ works. The new $a_i$ are $270, 272, 273, 276$; $N$ is $280$ and can now serve as $a_5$. The result is $270, 272, 273, 276, 280$.