I would hardly call the above "proof" of anything...I'd rather go as follows:
let . Now,
1) if , then the subset does the trick;
2) if , then does it;
3) Thus, we can reduce the problem where the set contains m natural numbers all of
which aren't multiples of m nor are there couples like in (2) above.
But then in cannot be more than equivalence classes modulo m, otherwise
condition (2) above applies.
Try now to take it from here