Saturday, January 28, 2012

The relatively prime graph

Wow, it's been some time since I've posted a puzzle!  Here's a simple pure math puzzle off the top of my head.

Back in middle/high school, I would kill time in classes drawing graph of all the points (n,m) such that n and m are relatively prime.  Relatively prime means that there is no integer greater than 1 which divides both n and m.  The graphs would look something like this:

The black squares represent (n,m) where n and m are relatively prime, while the white squares represent (n,m) where n and m are not relatively prime.

The question is, can you find a 3x3 white square somewhere in this graph?  In other words, find N and M such that (N,M) are not relatively prime, nor are the eight surrounding pairs, (N-1,M-1), (N,M-1), (N+1,M-1), (N-1,M), etc.

It's not a particularly elegant problem, but think of it as open-ended.  There are many solutions, and many methods will work to find them.  Can you find one?

solution posted