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


Secret Squïrrel said...

Ok, took me longer than I thought it would, but I have a sol'n. I won't post it in case anyone wants to work it out for themselves but the first digit of m,n is 2,7.

miller said...

You must have found a different solution than I. :-)

Secret Squïrrel said...

Well, there are rather a lot to choose from!

Secret Squïrrel said...

Ok, it's been a few days. The sol'n I found is m=231, n=7337. I didn't look for any others. My method wasn't particularly elegant but I managed to keep it relatively simple with a bit of trial-and-error at the end.

miller said...

Nice! Looking at your solution, I'm guessing that you searched pairs of numbers that each had three unique prime factors?

Secret Squïrrel said...

Basically, I decided that m and n should be odd. The corners of the 3×3 square would all be evenly div by 2 so I just had to worry about m sharing a factor with each of n-1, n, n+1 and vice versa. Obviously, they would need to be three different factors that m shared (likewise n).

One of m-1, m, m+1 and one of n-1, n, n+1 must have a factor of 3 so I assumed m to simply be a multiple of '3' and the next 2 smallest odd primes (3×5×7) and then looked at the prime factors for 104 and 106.

I tried making n equal to the product of one odd prime from each of 104,105,106 and looked to see if both n-1 and n+1 also shared a factor with m.

When none of the possible combinations worked, I briefly looked at m=3×5×11 but decided I might have a better chance of jagging a solution if at least one of m-1 / m+1 had 3 unique prime factors instead of only 2 as it would give me more possibilities for n. So then I tried m=3×7×11 and found n=7337. Ironically, there is a sol'n with m=3×5×11=165 - n is 10209.

Baumann Eduard said...

Ask for the smallest m+n

Baumann Eduard said...

By the way: please make a change of the link to me in
instead of

Unknown said...

I'd love to write a python program to find a solution for this.