# Is there a polynomial time algorithm for this decision problem?

Is there a factor in $$M$$ that is $$>$$ $$1$$, but $$<$$ $$M$$ that is NOT a factor of $$N$$?

False Result Example

$$N$$ = 8

$$M$$ = 16

1, 2, 4, 8, 16

There is no integer that is NOT a factor of $$N$$ that is $$>$$ $$1$$ but < $$M$$

True Result Example

$$N$$ = 2

$$M$$ = 26

1, 2, 13, 26

There is an integer $$13$$ which is NOT a factor of $$N$$ that is > 1 but < $$M$$

## Question

I have found a pseudo-polynomial solution, but is there a polynomial solution for this problem in the length of input?

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.