If you try to have 16 sides with your smallest interior angle being 120, your exterior angles start going negative. This is easy to see as the exterior angle is 180-(interior angle). Interior angles are 120,125...120+5(n-1). at n=13 the largest interior angle tries to be 180 deg and you no longer have a polygon.

Having only 9 sides satisfies your conditions above and remains a polygon.