# Coprime partition maximization problem

## Statement

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 .

## Particular cases

### 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.