For the NxN case, at least, there is a literature. An entry point is sequence A000938 in the On-Line Encyclopedia of Integer Sequences.
Gerry Myerson
- 39.9k
- 10
- 186
- 247