$m-1 \equiv n \pmod m$ - fast computation $m$ for given $n$

35 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

$$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.