Coprime partition maximization problem

Statement

Suppose $m$ and $n$ are natural numbers. The coprime partition maximization problem for $m$ with respect to $n$ asks for the maximum possible value of the smallest part in any unordered integer partition of $m$ for which every part is relatively prime to $n$.

Particular cases

Best and worst case

The best case for this problem is when $n$ and $m$ are relatively prime. In this case, the partition is the single-part partition, with the maximum being $m$ itself.

The worst case for this problem is when $n$ is divisible by all the primes less than or equal to $m$ (in other words, the square-free kernel of the factorial of $m$ divides $n$). In this case, the only permissible partition is the all ones partition, and the corresponding maximum is $1$.

Vinogradov's theorem and its implications on partitions

Fill this in later

The squareroot-size prime trick

If $p$ and $q$ are two primes whose product is less than $m$ such that neither divides $n$, then, by the postage stamp problem, we can write $n$ as a positive integer combination of $p$ and $q$. Thus, $\operatorname {min} (p,q)$ is a lower bound on the maximum possible value.