Is there a polynomial time algorithm for this decision problem?
This is hard as the integer factoring problem (simply take $N$ to be 2 or a random prime that has no factor in common with $M$).  Whether there is a polynomial-time algorithm for factoring is a famous open problem, but it is widely believed that there likely is no such algorithm.