I think if you hit full path coverage in each of them independently and run all the cases through both and check they're consistent you're still done.

Or branch coverage for the lesser version, the idea is still to generate interesting cases based on each implementation, not based solely on one of them.

If the buggy implementation relies indirectly on the assumption that 2^n - 1 is composite, by performing a calculation that's only valid for composite values on a prime value, there won't be a separate path for the failing case. If the Mersenne numbers don't affect flow control in a special way in either implementation, there's no reason for the path coverage heuristic to produce a case that distinguishes the implementations.