For the NxN case, at least, there is a literature. An entry point is sequence A000938 in the On-Line Encyclopedia of Integer Sequences.