On a condition for sums of odd numbers to yield prime numbers

134 Views Asked by At

I am a bit stuck trying to prove if the following statement is true or false:

Let it be $S_n=I_1+I_2+...+I_n$, where both the result and the terms of the sum are odd numbers greater than one. If for each partition of the terms of $S_n$ in two subsets of $s$ and $(n-s)$ terms it is verified that $\gcd (S_s, S_{n-s})=1$, where $S_s$ and $S_{n-s}$ are the partial sums of the terms in subsets $s$ and $(n-s)$ respectively, then $S_n$ is some prime number.

I would be grateful if you could share some counterexample (which I have not been able to find), or a way to prove or disprove the statement.

The condition imposes a great restriction on the possible divisors of $S_n$; as $S_n=S_s+S_{n-s}$, if for every pair of subsets $s$ and $(n-s)$ the condition is satisfied, it follows that $\gcd (S_s, S_{n-s})=\gcd (S_n, S_s)=\gcd (S_n, S_{n-s})= 1$ for every $S_s$ and $S_{n-s}$, which, applying combinatorics, would yield eventually a great number of non-possible divisors of $S_n$; so the statement makes sense, specially for sums with a great number of terms.

Indeed, maybe the statement could be false for sums with few number of terms, and true for sufficiently large $n$.

Thanks in advance!

EDIT

Thanks to @Stefan Albrecht, we have a counterexample to the statement for $n=3$. As suggested before, it would be great to determine if it exists some $N$ such that the statement is true for $n>N$.

1

There are 1 best solutions below

1
On BEST ANSWER

I'll assume that in the requirement that $\gcd(S_s,S_{n-s})=1$ for each partition of the terms, applies only to partitions for which the subsets $s$ and $n-s$ are nonempty, as otherwise the statement is vacuously true: If $s=\varnothing$ or $n-s=\varnothing$ then $$\gcd(S_s,S_{n-s})=\gcd(0,S_n)=S_n,$$ and so the requirement is never satisfied because clearly $S_n>1$.


Let $n$ be an odd positive integer and write $[n]:=\{1,\ldots,n\}$. Let $p>n$ be an odd prime number $p>n$ and set $$I_n=(p-1)\cdot p^{n-1}+n\qquad\text{ and }\qquad I_k=(p-1)\cdot p^{k-1}-1\quad\text{ for }1\leq k<n.$$ Then it is a bit of routine algebra to verify that $S_n=p^n$: \begin{eqnarray*} S_n&=&\big((p-1)\cdot p^{n-1}+n\big)+\sum_{k=1}^{n-1}((p-1)\cdot p^{k-1}-1)\\ &=&((p-1)\cdot p^{n-1}+n)+(p-1)\frac{p^{n-1}-1}{p-1}-(n-1)\\ &=&p^n. \end{eqnarray*} Claim: For every nonempty proper subset $s\subset\{1,\ldots,n\}$ we have $\gcd(S_s,S_{n-s})=1$.

Proof. First note that $\gcd(S_s,S_{n-s})$ divides $S_s+S_{n-s}=S_{n}$, so the gcd is a power of $p$. We have \begin{eqnarray*} I_1&\equiv&-2\pmod{p},\\ I_k&\equiv&-1\pmod{p}\quad\text{ for }1<k<n,\\ I_n&\equiv&\hphantom{-}n\pmod{p},\\ \end{eqnarray*} and so because $p>n$, we see that $S_s\equiv0\pmod{p}$ if and only if $s=\varnothing$ or $s=\{1,\ldots,n\}$. This means that for every nonempty proper subset $s\subset\{1,\ldots,n\}$ we have $\gcd(S_s,S_{n-s})=1$. $\square$


The argument also works if we replace $p$ by any integer $m>n$ with all prime factors greater than $n$, but the proof is a bit more cumbersome in the bookkeeping.