Of interest is that N has almost as many factors as $x^m - 1$, whether $x$ is a prime power or not.  So not only must $m$ be less than log N, m can't have more divisors than N has prime factors.  Thus for there to be any solution at all, the factors of N have to be a certain quantity and have a certain relative size. For example, if N=pq with p and q primes close in size, m cannot be 15.