Maximum GCD of partitions of a number. I came across a interesting theorem that, if we have a number n and we want to divide it into k parts such that sum of all k parts is equal to n, then the highest possible GCD of those partitions is equal to n/sum, where sum is the sum of 1+2+...k. I need the proof of this theorem and intuition behind it.
 A: Following Crostul's hint:
Suppose $d$ is the GCD of each element in the set $\{p_1,p_2..,p_k\}$ then, dividing each element by it, we get $\{a_1,a_2.,a_3..,a_k\}$. Allowing us to write:
$$ d(\sum_{i=1}^k a_i) = n$$
Or,
$$ d = \frac{n}{\sum_{i=1}^k a_i}$$
Of course since the elements are distinct, we can assume wlog that $a_i< a_{i+1}$, in the natural numbers (no 0), we can make the sum the least by replacing the elements by the least elements in the $\mathbb{N}$ while satisfying constraint.
From the above, we get the inequality:
$$ 1+2..+k \leq \sum_{i=1}^k a_i$$
Plugging this into the expression for $d$ isolated on LHS gives the result.
A: This theorem is not true.
As a counter-example, look at the case where $n = \alpha k$ (for $k > 1$).
Here, by setting the partitions all to equal size $\alpha$ we can get the GCD to be $\alpha = \frac{n}{k} > \frac{n}{1 + \cdots + k} $.
For the rest of this answer, I will assume that the theorem states that the partitions had to be distinct.
To prove this we start by naming $G(n, k)$ to be the largest such gcd you can find when splitting $n$ into $k$ distinct parts.
Now, we assume that $G(n,k) > \frac{n}{1+\cdots + k}$ (setting up a proof by contradiction).
Next then notice that the partitions are therefore of the form,
$$G(n, k) \alpha_1,G(n, k) \alpha_2, \ldots,G(n, k)\alpha_k$$
where $\alpha_i$ is a positive integer.
Now we since we know this is equal to $n$ we have
$$n = G(n,k) \left(\alpha_1 + \cdots + \alpha_k\right)$$
Now we pick the best possible case for our $\alpha_i$, clearly $gcd(\alpha_1, \ldots, \alpha_k) = 1$ otherwise, $G(n, k)$ would not be the largest possible. And finally, by selecting the smallest possible $\alpha_i = 1, 2, \ldots, k$.
We get that in the best case, $n = G(n, k)\left(1 + 2 + \cdots + k\right)$
$$\Rightarrow G(n,k) \not{>} \frac{n}{1 + 2 + \cdots + k}$$
$$\Rightarrow G(n,k) \leq \frac{n}{1 + 2 + \cdots + k}$$
