# Replacing the moduleo operation with occasional subtraction and one comparison

Suppose we have the following equation:

$$k_{i + 1} = (k_i + 2i + 1) \bmod{n}, \quad k_0=k, \quad i\ge 0$$

Show how we can we replace the mod with one comparison and occasional subtraction.

Attempt: I understood elsewhere that occasional here doesn't mean one subtraction. So, to replace modulo, the only way that I understood it is to keep subtracting $$k_{i + 1}$$ from $$n$$, but that means we should keep checking if it's less than $$n$$ or not each time, so we violate as I see it the one comparison limit if I am not wrong. Second, we are supposed to step once we get the comparison false, which will give a number between $$[0, n-1]$$ same as $$\bmod$$ would do? What do you think please?

Since $$0 \leq k_i < n$$, as long as $$i$$ is not too large, we will have $$0 \leq k_i + 2i+1 < 2n$$. Therefore you can compute the modulo by checking whether $$k_i+2i+1 \geq n$$, and if so, subtracting $$n$$.
This works as long as $$(n-1) + (2i+1) < 2n$$, that is, as long as $$i < n/2$$. Usually $$n$$ is very large, and so we are never going to perform $$n/2$$ many iterations.