Return to Revisions

In order for the remainder to be $r$ (where $0 \le r < \sqrt{N}$), we need $N-r$ to have an odd divisor $m$ with $r < m \le \sqrt{N}$. It can't happen if $N-r$ is prime; on the other hand, if $N-r$ is a product of many small primes there should be lots of such $m$.