I was trying to solve this problem. When I failed to come up with a memory efficient solution, I looked at some AC solutions.

Interestingly, the solutions used a property that states that the minimum number that has a phi value greater than or equal to a given number, must be the first prime number greater than the given number. For example, For 20, the answer is 23. I am looking for a formal proof of this property.