"The collection $\lbrace 8, 9, 12\rbrace$ is a set of three positive integers with the property that, given any
two of these integers, their greatest common factor (gcf) is equal to their difference:
- $\text{gcd}(8,9)=1=9−8$;
- $\text{gcd}(8,12)=4=12−8$;
- $\text{gcd}(9,12)=3=12−9$.
Can you find a set of four integers with the same property? What about a set of $n$ integers?"
I have come up with more examples of two integer pairs (example: $\lbrace 84,112 \rbrace$) but can't seem to work out a 'formula' or a general case to build up to the $4$ integer case or even the $n$ integer case.
Best Answer
Yes, you can create sets as big as you want and this can be proved by induction:
For $n=2$ you can take set $\{1,2\}$ as the solution. Now the induction step:
Now suppose that such set exists for some $n$ and denote that set with $S_n=\{a_i\mid i=1,2,...,n\}$.
Calculate all differencies $d_{jk}$ between all pairs of elements $a_j<a_k$ picked from the set $S_n$. Notice that:
$$d_{jk}=a_k-a_j=\gcd(a_j,a_k)\tag{1}$$
Find the least common multiple for all $d_{jk},a_i$:
$$L=LCM \left(\{d_{jk}=a_k-a_j\mid 1\le j <k\le n\}\cup \{a_i\mid i=1,2,...,n\}\right)\tag{2}$$
Check the following set with $n+1$ elements:
$$S_{n+1}=\{L\}\cup\{L+a_i\mid i=1,2,...,n\} $$
Firstly, take any two elements from the extend set different from $L$:
$$\gcd(L+a_j, L+a_k)=\gcd(L+a_j, a_k-a_j)=\gcd(L+a_j, d_{jk})$$
According to (1) and (2) we know that $d_{jk}\mid a_j$ and $d_{jk}\mid L$. Therefore:
$$\gcd(L+a_j, L+a_k)=d_{jk}=a_k-a_j=(L+a_k)-(L+a_j)$$
Secondly, if you pick $L$ and $L+a_j$:
$$\gcd(L, L+a_j)=\gcd(L, a_j)=a_j=(L+a_j)-L$$
The last is obvious as per definition of $L$ ($a_j\mid L$).
Now, the fun part. Start with:
$$S_2=\{1,2\}$$
and apply the algorithm described above, you get the following sequence of solutions with rapidly growing numbers:
$$S_3=\{2, 3, 4\}$$
$$S_4=\{12, 14, 15, 16\}$$
$$S_5=\{1680, 1692, 1694, 1695, 1696\}$$
$$S_6=\{343319185440, 343319187120, 343319187132, 343319187134, 343319187135, \ 343319187136\}$$
$$S_7=\{118295944058236539689200180716000759951728985298370880, \ 118295944058236539689200180716000759951729328617556320, \ 118295944058236539689200180716000759951729328617558000, \ 118295944058236539689200180716000759951729328617558012, \ 118295944058236539689200180716000759951729328617558014, \ 118295944058236539689200180716000759951729328617558015, \ 118295944058236539689200180716000759951729328617558016\}$$
So the method is far from optimal and finding the "smallest" set for a given $n$ is still a challenge. But you can create as long a sequence as you want.
(I have solved a similar but not completely identical problem here but the same logic is applicable here too.)