The equivalence classes modulo some n form a partition of the integers so you can use that to create a very efficient solution with very little code.

Here is a neat explanation:

https://preshing.com/20121224/how-to-generate-a-sequence-of-...

If you need even better properties (eg cryptographically secure) you can also look at PCG with k-dimensional equidistribution:

http://www.pcg-random.org/index.html