See the original problem
This is the solution I found:
I tried searching for solutions for which N and M are odd. That way I automatically get that 2 is a common factor of N+1, N-1, M+1, and M-1.
N needs to have a factor in common with M, M+1, and M-1. Therefore, N needs at least 3 distinct prime factors. N is odd, so the smallest N fitting this criteria is 3*5*7=105.
104 has prime factors 2 and 13. 106 has prime factors 2 and 53. Therefore, M needs to have factors 13 and 53. That is, M needs to be a multiple of 689. The rest of my search consisted of trying different odd multiples of 689 until one worked.
There are many other methods to find a solution (and many other solutions), but that's mine.