I think this is not a problem because 59 nor 509 are in the list of prime numbers used (on the left side). Euclid's proof merely states that for every list of prime numbers, there's a new one, not in the list. https://en.wikipedia.org/wiki/Euclid%27s_theorem#Euclid's_pr...
Yes, that's the point -- Euclid's proof doesn't require that, it works like you said; but it's a widespread misconception that it does work that way. It's a counterexample to the misconception, not to the real proof.