$\frac{1}{d_1} + \dots + \frac{1}{d_k} = 1,$ and $\gcd(d_i,d_j)>1 \, \forall i,j$ implies $\gcd(d_1, \dots, d_k) > 1$ for distinct $d_i.$

91 Views Asked by At

Conjecture: If $d_i \in \mathbb{N}$ are distinct, $\frac{1}{d_1} + \dots + \frac{1}{d_k} = 1,$ and $\gcd(d_i,d_j)>1 \, \forall i,j,$ then $\gcd(d_1, \dots, d_k) > 1.$

Motive: In the process of solving a question related to covering $\mathbb{N}$ with arithmetic progressions, I found that the following statement would allow me to finish my proof by contradiction.

Clearly, the conjecture is true if any of $d_1, \dots, d_k$ are prime powers. If none of them are prime powers, then they must be among $6, 10, 12, 14, 15, 16, 18, 20, 21, \dots$ Since $S = \frac{1}{6}+ \frac{1}{10}+ \frac{1}{12}+ \frac{1}{14}+ \frac{1}{15}+ \frac{1}{16}+ \frac{1}{18}+ \frac{1}{20}+ \frac{1}{21} + \frac{1}{22}+\frac{1}{24}+\frac{1}{26}+\frac{1}{28}+\frac{1}{30}+\frac{1}{33}+\frac{1}{34}+\frac{1}{35} < 1 < S + \frac{1}{36},$ any counterexample must have $k \ge 18.$ But including a number with $2$ distinct prime divisiors severely restricts the numbers we are allowed to take afterwards, so we could perform further casework and make the bound for a potential counterexample higher and higher.

Warning: You cannot rely solely on analysis because if $=1$ is replaced with $\ge 1,$ the result is false. There are $2$ constructions that demonstrate this:

$\{6, 10, 15\} \cup \{30a : a \le n\}$ for $n$ large enough.

$\{2 \cdot 3 \cdot 5 \cdot 7 = 210\} \cup S'$ where $S'$ is a finite subset of $S = \{2^a 3^b 5^c : \text{at most one of } a, b, c \text{ is zero}\}$ with sum $\ge 209/210.$ This is possible since $\sum\limits_{s \in S} \frac{1}{s} = 1.$

1

There are 1 best solutions below

2
On

The conjecture is false. It is well-known that any positive rational can be obtained as a sum of a finite subsequence of the harmonic series. Let $$\frac{1}{c_1} + \frac{1}{c_2} + \dots + \frac{1}{c_k} = 30(1 - 1/6 - 1/10 - 1/15) = 20$$ where the $c_i$ are distinct. Now we can let $d_1 = 6, d_2 = 10, d_3 = 15, d_{3+i} = 30c_i$ for $1 \le i \le k.$