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

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?

• Really like the diagram here. Sep 19, 2023 at 11:24
• additional constraint: it must be a valid QR code :) Sep 20, 2023 at 17:53

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$$

• But how would you go about finding a solution with $N$ and $M$ both even? Is that worthy of a sequel? Sep 19, 2023 at 22:58
• @DanielMathias The general idea would be the same but you would need to consider more prime factors to get all the required common divisors so the solutions would get bigger. Sep 20, 2023 at 6:02

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)

• 4x4 would contain 3x3 with $N$ and $M$ both even. The first of those is $(87374,202476)$ Sep 20, 2023 at 22:53
• great find Daniel! Sep 20, 2023 at 23:12
• $(18291,90116)$ Sep 21, 2023 at 21:41
• There are arbitrarily long white rectangles of width one. Consider, for example, 50! = 1x2x3...50. Note that 50! and 50!+2 have a common factor of 2. 50! and 50!+3 have a common factor of 3. 50! and 50!+4 have a common factor of 4. This pattern continues. 50! and 50!+49 have a common factor of 49. 50! and 50!+50 have a common factor of 50. So there is a white rectangle whose size is at least 1x49. By choosing even bigger factorials, we can get even larger white rectangles. Sep 27, 2023 at 22:08