Divisibility of cyclic sums

296 Views Asked by At

Lately I have been studying the divisibility of some cyclic sums, and I was wondering about the following

Conjecture

Let it be a set of distinct positive integers $S=\{x_1,x_2,...,x_n\}$ such that $2\leq{x_1}<x_2<...<x_n$. Then,

$$\prod_{k=1}^{n}x_{k}\nmid\left(\sum_{cyc}\left(\prod_{k=1}^{n-1}x_{k}\right)+\sum_{cyc}\left(\prod_{k=1}^{n-2}x_{k}\right)+...+\sum_{k=1}^nx_k\right)$$

I would appreciate any help regarding this conjecture proof or refutation.

I already noted that there exist sets of distinct integers $S=\{x_1,x_2,...,x_n\}$ such that $$\prod_{k=1}^{n}x_{k}\mid\sum_{cyc}\left(\prod_{k=1}^{n-1}x_{k}\right)$$

For example, for $S=\{2,3,6\}$, $$2*3*6\mid (2*3)+(3*6)+(6*2)$$

Thanks in advance!

EDIT

I found that the conjecture is true if $\min\{x_1,x_2,...,x_n\}>n$, as it follows from the following

Proof

Assuming $x_{1}=x_{2}=...=x_{n}=n+1$, we get that

$$\prod_{k=1}^{n}x_{k}=\left(n+1\right)^{n}$$

$$\left(\sum_{cyc}\left(\prod_{k=1}^{n-1}x_{k}\right)+\sum_{cyc}\left(\prod_{k=1}^{n-2}x_{k}\right)+...+\sum_{k=1}^{n}x_{k}\right)=n\left(\left(n+1\right)^{n-1}+\left(n+1\right)^{n-2}+...+\left(n+1\right)\right)$$

$$n\left(\left(n+1\right)^{n-1}+\left(n+1\right)^{n-2}+...+\left(n+1\right)\right)=\left(\left(n+1\right)-1\right)\left(\left(n+1\right)^{n-1}+\left(n+1\right)^{n-2}+...+\left(n+1\right)\right)$$

$$\left(\left(n+1\right)-1\right)\left(\left(n+1\right)^{n-1}+\left(n+1\right)^{n-2}+...+\left(n+1\right)\right)=\left(n+1\right)^{n}-\left(n+1\right)$$

Subsequently,

$$\left(\sum_{cyc}\left(\prod_{k=1}^{n-1}x_{k}\right)+\sum_{cyc}\left(\prod_{k=1}^{n-2}x_{k}\right)+...+\sum_{k=1}^{n}x_{k}\right)=\left(n+1\right)^{n}-\left(n+1\right)$$

Thus,

$$\prod_{k=1}^{n}x_{k}>\left(\sum_{cyc}\left(\prod_{k=1}^{n-1}x_{k}\right)+\sum_{cyc}\left(\prod_{k=1}^{n-2}x_{k}\right)+...+\sum_{k=1}^{n}x_{k}\right)$$

And therefore,

$$\prod_{k=1}^{n}x_{k}\nmid\left(\sum_{cyc}\left(\prod_{k=1}^{n-1}x_{k}\right)+\sum_{cyc}\left(\prod_{k=1}^{n-2}x_{k}\right)+...+\sum_{k=1}^{n}x_{k}\right)$$

Subsequently, the conjecture is true if $\min\{x_1,x_2,...,x_n\}>n$.

1

There are 1 best solutions below

7
On BEST ANSWER

The conjecture is true for $n=2$ since $$\small x_1+x_2=kx_1x_2\implies (kx_1-1)(kx_2-1)=1\implies kx_1-1=kx_2-1\implies x_1=x_2$$


The conjecture is false for $n=3$ since for $(x_1,x_2,x_3)=(2,4,14)$, we have$$\frac{x_1x_2+x_2x_3+x_3x_1+x_1+x_2+x_3}{x_1x_2x_3}=1$$


The conjecture is false for every $n\ge 3$.

Proof :

Let $$S(x_1,x_2,\cdots,x_n):=\sum_{cyc}\left(\prod_{k=1}^{n-1}x_{k}\right)+\sum_{cyc}\left(\prod_{k=1}^{n-2}x_{k}\right)+...+\sum_{k=1}^nx_k$$

We have $$S(x_1,x_2,\cdots,x_n)=S(x_1,x_2,\cdots,x_{n-1})+x_nS(x_1,x_2,\cdots,x_{n-1})+x_n+\prod^{n-1}_{k=1}x_k$$

So, taking $$x_n=S(x_1,x_2,\cdots,x_{n-1})+\prod^{n-1}_{k=1}x_k$$ we get $$\frac{S(x_1,x_2,\cdots,x_n)}{\displaystyle\prod_{k=1}^{n}x_k}=\frac{2+S(x_1,x_2,\cdots,x_{n-1})}{\displaystyle\prod_{k=1}^{n-1}x_k}=\frac{2+S(x_1,x_2,\cdots,x_{n-2})+x_{n-1}S(x_1,x_2,\cdots,x_{n-2})+x_{n-1}+\displaystyle\prod^{n-2}_{k=1}x_k}{\displaystyle\prod_{k=1}^{n-1}x_k}$$

Now, taking $$x_{n-1}=2+S(x_1,x_2,\cdots,x_{n-2})+\prod^{n-2}_{k=1}x_k$$ we get $$\frac{S(x_1,x_2,\cdots,x_n)}{\displaystyle\prod_{k=1}^{n}x_k}=\frac{2+S(x_1,x_2,\cdots,x_{n-1})}{\displaystyle\prod_{k=1}^{n-1}x_k}=\frac{2+S(x_1,x_2,\cdots,x_{n-2})}{\displaystyle\prod_{k=1}^{n-2}x_k}$$

Similarly, taking $$x_{i}=2+S(x_1,x_2,\cdots,x_{i-1})+\prod^{i-1}_{k=1}x_k$$ for $i=3,4,\cdots,n-2$, we get $$\frac{S(x_1,x_2,\cdots,x_n)}{\displaystyle\prod_{k=1}^{n}x_k}=\frac{2+S(x_1,x_2)}{\displaystyle\prod_{k=1}^{2}x_k}=\frac{2+x_1+x_2}{x_1x_2}$$ which equals $1$ when $(x_1,x_2)=(2,4)$.

So, a counterexample is $$x_i=\begin{cases}S(x_1,x_2,\cdots,x_{n-1})+\displaystyle\prod^{n-1}_{k=1}x_k&\ \ \text{if $\ \ i=n$} \\\\2+S(x_1,x_2,\cdots,x_{i-1})+\displaystyle\prod^{i-1}_{k=1}x_k&\ \ \text{if $\ \ 3\le i\le n-1$} \\\\4&\ \ \text{if $\ \ i=2$}\\\\2&\ \ \text{if $\ \ i=1$}\end{cases}$$ where $$S(x_1,x_2,\cdots,x_n)=\sum_{cyc}\left(\prod_{k=1}^{n-1}x_{k}\right)+\sum_{cyc}\left(\prod_{k=1}^{n-2}x_{k}\right)+...+\sum_{k=1}^nx_k$$

For example,

  • $(x_1,x_2,x_3,x_4)=(2,4,16,254)$ is a counterexample for $n=4$.

  • $(x_1,x_2,x_3,x_4,x_5)=(2,4,16,256,65534)$ is a counterexample for $n=5$.$\quad\blacksquare$


Added :

Let $$S(x_1,x_2,\cdots,x_n):=\sum_{cyc}\left(\prod_{k=1}^{n-1}x_{k}\right)+\sum_{cyc}\left(\prod_{k=1}^{n-2}x_{k}\right)+...+\sum_{k=1}^nx_k$$

Let us call your conjecture Conjecture 1.

Conjecture 1 : If $x_1,x_2,\cdots,x_n$ are positive integers satisfying $2\le x_1\lt x_2\lt\cdots\lt x_n$, then $\displaystyle\prod_{k=1}^{n}x_k\not\mid S(x_1,x_2,\cdots,x_n)$.

We've already seen that Conjecture 1 is true for $n=2$, and is false for $n\ge 3$.

Now, let us consider the following conjecture :

Conjecture 2 : If $x_1,x_2,\cdots,x_n$ are positive integers satisfying $2\le x_1\lt x_2\lt\cdots\lt x_n$ and $\color{red}{\gcd(x_1,x_2,\cdots,x_n)=1}$, then $\displaystyle\prod_{k=1}^{n}x_k\not\mid S(x_1,x_2,\cdots,x_n)$.

Conjecture 2 is true for $n=2$ since Conjecture 1 is true for $n=2$.

In the following, I'm going to prove the following claim :

Claim : Conjecture 2 is true for $n=3,4$.

Proof :

Let $A:=S(x_1,x_2,x_3)$.

Suppose that there are positive integers $x_1,x_2,x_3$ satisfying $2\le x_1\lt x_2\lt x_3, \gcd(x_1,x_2,x_3)=1$ and $x_1x_2x_3\mid A$.

If exactly one of $x_1,x_2,x_3$ is even, then $A$ is odd, so $x_1x_2x_3\not\mid A$.

If exactly one of $x_1,x_2,x_3$ is odd, then $A$ is odd, so $x_1x_2x_3\not\mid A$.

So, we see that $x_1,x_2,x_3$ have to be odd to have $$x_1x_2x_3\mid A\implies x_1x_2x_3\mid \frac A2\implies \frac A2\ge x_1x_2x_3\implies 4A\ge 8x_1x_2x_3$$

$$\implies X_1X_2X_3\le 3(X_1+X_2+X_3)+10$$ $$\implies X_1X_2\le 3\bigg(\frac{X_1}{X_3}+\frac{X_2}{X_3}+1\bigg)+\frac{10}{X_3}\lt 3\times 3+\frac{10}{13}\lt 10\tag1$$ where $X_i:=2x_i-1$ for $i=1,2,3$.

Also, since $x_1\ge 3$ and $x_2\ge 5$, we have $$X_1X_2=(2x_1-1)(2x_2-1)\ge 5\times 9=45\tag2$$

There is no $(x_1,x_2)$ satisfying both $(1)$ and $(2)$.

So, Conjecture 2 is true for $n=3$.

Next, let $B:=S(x_1,x_2,x_3,x_4)$.

Suppose that there are positive integers $x_1,x_2,x_3,x_4$ satisfying $2\le x_1\lt x_2\lt x_3\lt x_4, \gcd(x_1,x_2,x_3,x_4)=1$ and $x_1x_2x_3x_4\mid B$.

If exactly one of $x_1,x_2,x_3,x_4$ is even, then $B$ is odd, so $x_1x_2x_3x_4\not\mid B$.

If exactly two of $x_1,x_2,x_3,x_4$ are even, then $B$ is odd, so $x_1x_2x_3x_4\not\mid B$.

If exactly three of $x_1,x_2,x_3,x_4$ is odd, then $B$ is odd, so $x_1x_2x_3x_4\not\mid B$.

So, we see that $x_1,x_2,x_3,x_4$ have to be odd to have $$x_1x_2x_3x_4\mid B\implies x_1x_2x_3x_4\mid \frac B2\implies \frac B2\ge x_1x_2x_3x_4\implies 8B\ge 16x_1x_2x_3x_4$$

$$\implies X_1X_2X_3X_4\le 3(X_1X_2+X_1X_3+X_1X_4+X_2X_3+X_2X_4+X_3X_4)+12(X_1+X_2+X_3+X_4)+31$$ $$\implies X_1X_2\le 3\bigg(\frac{X_1X_2}{X_3X_4}+\frac{X_1}{X_4}+\frac{X_1}{X_3}+\frac{X_2}{X_4}+\frac{X_2}{X_3}+1\bigg)+12\bigg(\frac{X_1}{X_3X_4}+\frac{X_2}{X_3X_4}+\frac{1}{X_3}+\frac{1}{X_4}\bigg)+\frac{31}{X_3X_4}$$ $$\lt 3\times 6+12\bigg(2+\frac{1}{13}+\frac{1}{17}\bigg)+\frac{31}{13\times 17}=\frac{569}{13}\lt 44\tag3$$

where $X_i:=2x_i-1$ for $i=1,2,3,4$.

Also, since $x_1\ge 3$ and $x_2\ge 5$, we have $$X_1X_2=(2x_1-1)(2x_2-1)\ge 5\times 9=45\tag4$$

There is no $(x_1,x_2)$ satisfying both $(3)$ and $(4)$.

So, Conjecture 2 is true for $n=3,4$.$\quad\blacksquare$