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$


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.