Can you find a 3x3 white square somewhere in this relatively prime graph?

Question

---

_{This puzzle comes from: http://skepticsplay.blogspot.com/search/label/puzzles}

---

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 a 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 graph 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?

Answer 1

One solution I've found

$M = 6201, N = 105$

Construction

Without loss of generality, I will assume $M>N$. If we set $M$ and $N$ to both be odd, then we will immediately get that $N-1$, $N+1$, $M-1$ and $M+1$ all share a common factor of $2$ and so the cells representing intersections of these numbers will be white. It suffices to find $M$ and $N$ such that $N-1$, $N$ and $N+1$ all share a common factor with $M$ and that $M-1$ and $M+1$ share a common factor with $N$.

This means that $N$ should have at least three relatively prime odd factors. For starters let's try setting $N = 3 \times 5 \times 7 = 105$. This means we must find $M$ such that $M-1$, $M$ and $M+1$ are each divisible by one of $3,5,7$. Additionally, since $N-1 = 104 = 8 \times 13$ and $N+1 = 106 = 2 \times 53$, it must be that $M$ is divisible by $13 \times 53 = 689$.

Now,
$689 \equiv 2\mod 3$,
$689 \equiv 4\mod 5$
$689 \equiv 3\mod 7$
To complete, it suffices to find a multiple of $689$ which has residues $-1,0$ and $1$ when divided by $3,5,7$, in some order.

If we simply focus on multiples which are powers of $3$ and look at the residues modulo $5$ and $7$, we quickly find that
$689 \times 3^2 \equiv 1\mod 5$
$689 \times 3^2 \equiv -1\mod 7$
Hence this yields a solution for $M = 689 \times 9 = 6201$

Answer 2

Cool puzzle! In my notation $(N,M)$ is the top-left corner of the white sub-grid. I used a computer program to find 99 solutions for $N \leq M \leq 10000$:

(104, 6200), (230, 5654), (230, 7104), (230, 7336), (494, 5300), (594, 3128), (644, 5718), (650, 5704), (664, 4730), (740, 4654), (740, 6992), (824, 7930), (968, 6764), (1000, 3794), (1000, 5564), (1000, 5654), (1064, 6460), (1104, 8294), (1274, 1308), (1274, 6408), (1274, 6698), (1274, 7104), (1308, 8294), (1442, 9176), (1448, 2714), (1462, 7258), (1598, 3484), (1728, 7124), (1748, 6094), (1884, 2000), (1924, 2330), (1924, 4640), (1924, 4718), (1924, 5654), (1988, 8294), (2210, 3080), (2254, 2540), (2254, 5984), (2288, 7084), (2364, 2924), (2408, 4234), (2408, 5984), (2430, 5642), (2464, 6698), (2464, 8294), (2484, 6104), (2484, 7028), (2624, 3730), (2664, 7954), (2716, 7370), (2750, 8384), (2794, 8084), (2914, 4928), (3014, 9580), (3170, 9814), (3310, 6104), (3344, 7580), (3534, 5150), (3794, 4598), (3794, 4640), (3794, 5620), (4024, 7544), (4146, 4640), (4234, 4598), (4234, 5654), (4520, 4794), (4640, 4674), (4640, 7384), (4640, 9294), (4654, 7370), (4674, 6698), (4674, 8294), (4718, 5368), (4718, 5564), (4730, 5394), (4878, 5984), (5024, 5494), (5074, 6320), (5082, 5796), (5300, 7314), (5564, 7578), (5564, 8238), (5564, 9294), (5620, 5984), (5654, 8994), (5984, 8568), (6068, 7174), (6250, 8834), (6278, 9854), (6764, 8074), (6968, 7474), (6984, 7874), (7124, 7370), (7314, 7964), (7656, 9176), (8294, 9162), (8568, 8854), (9064, 9470), (9176, 9268)

I couldn't find any 4x4 or 14x1 solutions for $N \leq M \leq 20000$. However, I did find 84 13x1 solutions for $N \leq M \leq 10000$:

(114, 2310), (114, 4620), (114, 5610), (114, 6930), (114, 9240), (294, 2730), (294, 4830), (294, 5460), (294, 8190), (294, 9660), (774, 6270), (864, 4290), (864, 8580), (954, 6510), (1074, 8970), (1134, 3570), (1134, 7140), (1344, 3990), (1344, 7980), (1584, 7770), (1584, 9030), (1644, 6630), (1764, 6090), (1764, 9570), (1914, 9690), (2184, 2310), (2184, 4620), (2184, 6930), (2184, 9240), (2424, 2730), (2424, 3570), (2424, 4620), (2424, 5460), (2424, 6930), (2424, 7140), (2424, 8190), (2424, 9240), (2634, 3990), (2634, 7410), (2634, 7980), (3024, 5460), (3024, 8190), (3234, 8610), (3414, 4290), (3414, 8580), (3744, 7590), (3834, 7590), (3894, 9870), (4314, 6090), (4494, 4620), (4494, 6930), (4494, 9240), (4524, 4830), (4524, 9660), (4704, 7140), (4734, 6930), (4734, 9240), (4764, 7410), (4974, 6630), (5124, 9660), (5154, 5460), (5154, 8190), (5154, 8580), (5334, 7980), (5364, 8610), (5484, 5610), (5484, 6270), (5544, 6510), (5754, 8190), (5964, 9870), (5994, 7140), (6174, 7770), (6624, 7980), (6804, 6930), (6804, 9240), (7044, 9240), (7434, 9030), (7704, 8580), (7764, 9690), (7794, 9570), (7884, 8190), (7884, 8970), (9114, 9240), (9354, 9660)