Given a number $n$ and an Interval $I = [ \; \lfloor n^{1/4} \rfloor, \lfloor n^{(1/3) \rfloor \;} ]$, can we say anything about the distribution of $\{ n \mod b \;\;| \; b \in I \}$?

  1. In particular, if I wanted the residue to be close to any region in $[0, b-1]$, say close to the "top" of the residue classes around $b-1$ could I choose a $b$ for which that is the case without doing much work? By not doing much work I mean not having to try every single $b$ in the interval $I$ until I find one.

  2. Could I somehow choose better $b$'s in my search than just randomly trying them; or even better, just choose the right $b$ in one go.

The factorization of $n$ is known if that helps any.

Heuristically, it seems most residues tend to be close to the "top", but I just need to $b$'s where I will know where the residues will land without having to try all of them.


1 Answer 1


Note that $n \equiv b-1 \pmod b$ implies $b | n+1$, $n \equiv b-2 \pmod b$ implies $b | n+2$, and so on. Therefore you can factor $n+1$, $n+2$, and so on, until one of them has a factor in $I$. You can do something similar for other target regions.

While I don't have a proof, empirically it seems like you only need to factor $O(1)$ numbers on average, because around half of the numbers $n$ I've checked have a divisor in the range $[n^{\frac14},n^{\frac13}]$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.