Coprime partition maximization problem
Suppose and are natural numbers. The coprime partition maximization problem for with respect to asks for the maximum possible value of the smallest part in any unordered integer partition of for which every part is relatively prime to .
Best and worst case
The best case for this problem is when and are relatively prime. In this case, the partition is the single-part partition, with the maximum being itself.
The worst case for this problem is when is divisible by all the primes less than or equal to (in other words, the square-free kernel of the factorial of divides ). In this case, the only permissible partition is the all ones partition, and the corresponding maximum is .
Vinogradov's theorem and its implications on partitions
Fill this in later
The squareroot-size prime trick
If and are two primes whose product is less than such that neither divides , then, by the postage stamp problem, we can write as a positive integer combination of and . Thus, is a lower bound on the maximum possible value.