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


  [1]: http://www2.research.att.com/~njas/sequences/A000938