6
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ @Peter What about 36, 40, 42, 45, 48? $\endgroup$ – FredH Feb 19 at 13:59
  • $\begingroup$ @FredH You are right, I made a mistake in my program. $\endgroup$ – Peter Feb 19 at 14:02
  • 1
    $\begingroup$ For the record, 6-tuples exist as well, starting with 210, 216, 220, 224, 225, 240. $\endgroup$ – FredH Feb 19 at 14:45
  • 2
    $\begingroup$ Sorry to not have any theory to offer, but it may nevertheless be of interest to know that the first $7$-tuple seems to be $14976, 14980, 14994, 15000, 15008, 15015, 15120$. I'll leave it at that. $\endgroup$ – FredH Feb 19 at 15:29
  • 1
    $\begingroup$ See my answer to this question $\endgroup$ – steven gregory Feb 20 at 7:00
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great use of brute force coding! But what is the theory behind this? So by brute force we found that we could get find 4 numbers, and 5... But who's to say that we could find 2000, or 9000000? Is there an upper limit or can we find an arbitrary number? $\endgroup$ – Wesley Feb 19 at 14:57
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's +2 for the last even number start property actually, forgot to include the start number. Start number +1 never works except odd prime starts to my knowledge. okay last part here only works for 3. $\endgroup$ – Roddy MacPhee Feb 19 at 19:18
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Somehow I haven't been able to follow this. I'm sure I'm being dense, but would you please add a little more detail to step 4? How do we know we can find such a $k?$ $\endgroup$ – saulspatz Feb 23 at 16:44
  • 1
    $\begingroup$ @saulspatz The congruence $a_j + km \equiv 0 \pmod {q_j}$ can be solved for $k$ because $m$ (being a divisor of $M$) is coprime to $q_j$. $\endgroup$ – FredH Feb 23 at 21:18
  • $\begingroup$ Actually, $m$ is only guaranteed to be a divisor of $M$ the first time Step 4 is executed; thereafter it acquires factors of various $q_i$, but remains coprime to the others, since the $q_i$ are pairwise coprime. $\endgroup$ – FredH Feb 23 at 21:49
  • $\begingroup$ I think that hits the point I was having most trouble with. I couldn't understand why you made the requirement that the $q_i$ be coprime to one another. I still need to go back over this, but now I feel like I know what's going on. Excellent answer, but the way. I don't understand why it's not getting upvotes/acceptance. $\endgroup$ – saulspatz Feb 23 at 22:16
  • $\begingroup$ @saulspatz There haven't been a lot of views of this question, and, as Steven Gregory pointed out half an hour after my answer, it's been done before. $\endgroup$ – FredH Feb 23 at 22:29

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.