We have very big number $n$ and we are looking for such numbers $m$ satisfying the following condition:

$$m-1 \equiv n \pmod m$$

We only know that $n$ is integer (positive).

There is some very quick method, how can it be calculated? (sequential checking of successive numbers is tragically slow)

If such a method exists then I will ask for information about it and its computational complexity.


$$m - 1 \equiv n\pmod{m}$$

is equivalent to

$$n+1 \equiv 0 \pmod m$$

$m$ are the factors of $n+1$. The complexity of the problem is equivalent to factorization.


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.