I'm trying to solve the following problem: given an integer $n$, under which conditions of $n$ the following statement is true:
For any $1 < k \leq n$, there is always a partition of $k$ parts of $n$ so that each part is coprime with $n$.
Here is what I obtained:
- The statement is obviously true if $n$ is prime,
- If $n > 2$ then $n$ is odd since $2$ must occur in the partition of $n-1$ part of $n$.
I think that the condition should be:
$n$ is either $2$ or an odd number.
I've tried several numbers, for example $9$ (the first odd number which is not prime):
$$\begin{align*}9 &= 1 + \dots + 1 \\ &= \dots \\ &= 1 + 4 + 4 \\ &= 1 + 8 \end{align*}$$
Using the trick of grouping powers of $2$, I've found that if $n = (a_1 \dots a_i)_{m}$ for some base $m$ where $gcd(m,n) = 1$, then there is always a partition of $k$ part where $\sum\limits_{j=1}^{i} a_j \leq k \leq n$. Then I found that $15$, $21$ are ok too.
For example:
- $15 = 1111_2$, so I can find partition until $1+1+1+1 = 4$ parts, and
- $15 = 21_7$, so I can find partition until $2+1 = 3$ parts, finally
- $15 = 11_{14}$, so I can find partition until $1+1= 2$ parts.
and:
- $21 = 10101_{2}$, so until $3$,
- $21 = 11_{20}$, so until $2$.