Coprime partition maximization problem

From Number
Jump to: navigation, search


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.