Maior fator comum

Question

"A coleção $\lbrace 8, 9, 12\rbrace$ é um conjunto de três inteiros positivos com a propriedade de que, dados quaisquer dois desses inteiros, seu maior fator comum (gcf) é igual à diferença:

• $\text{gcd}(8,9)=1=9−8$;
• $\text{gcd}(8,12)=4=12−8$;
• $\text{gcd}(9,12)=3=12−9$.

Você consegue encontrar um conjunto de quatro inteiros com a mesma propriedade? Que tal um conjunto de$n$ inteiros? "

Eu vim com mais exemplos de dois pares inteiros (exemplo: $\lbrace 84,112 \rbrace$), mas não consigo descobrir uma 'fórmula' ou um caso geral para construir o $4$ caso inteiro ou mesmo o $n$ caso inteiro.

Answer 1

Sim, você pode criar conjuntos tão grandes quanto quiser e isso pode ser provado por indução:

Para $n=2$ você pode pegar o set $\{1,2\}$como a solução. Agora, a etapa de indução:

Agora, suponha que tal conjunto exista para alguns $n$ e denotar esse conjunto com $S_n=\{a_i\mid i=1,2,...,n\}$.

Calcule todas as diferenças $d_{jk}$ entre todos os pares de elementos $a_j<a_k$ escolhido do conjunto $S_n$. Notar que:

$$d_{jk}=a_k-a_j=\gcd(a_j,a_k)\tag{1}$$

Encontre o mínimo múltiplo comum para todos $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}$$

Verifique o seguinte conjunto com $n+1$ elementos:

$$S_{n+1}=\{L\}\cup\{L+a_i\mid i=1,2,...,n\} $$

Em primeiro lugar , pegue quaisquer dois elementos do conjunto extend diferente de$L$:

$$\gcd(L+a_j, L+a_k)=\gcd(L+a_j, a_k-a_j)=\gcd(L+a_j, d_{jk})$$

De acordo com (1) e (2), sabemos que $d_{jk}\mid a_j$ e $d_{jk}\mid L$. Portanto:

$$\gcd(L+a_j, L+a_k)=d_{jk}=a_k-a_j=(L+a_k)-(L+a_j)$$

Em segundo lugar , se você escolher$L$ e $L+a_j$:

$$\gcd(L, L+a_j)=\gcd(L, a_j)=a_j=(L+a_j)-L$$

O último é óbvio de acordo com a definição de $L$ ($a_j\mid L$)

Agora, a parte divertida. Começar com:

$$S_2=\{1,2\}$$

e aplicar o algoritmo descrito acima, você obtém a seguinte sequência de soluções com números de crescimento rápido:

$$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\}$$

Portanto, o método está longe de ser ideal e encontrar o "menor" conjunto para um determinado $n$ainda é um desafio. Mas você pode criar uma sequência tão longa quanto desejar.

(Resolvi um problema semelhante, mas não completamente idêntico aqui, mas a mesma lógica se aplica aqui também.)