To see how this works we note first that \begin{equation} (aN_{i-1}) \mathrm{MOD} (M)= (aN_{i-1}-[N_{i-1}/q]M)\mathrm{MOD} (M), \tag{16} \end{equation} since we can add or subtract any integer multiple of M from aN_{i-1} . The last term [N_{i-1}/q]M\mathrm{MOD}(M) is zero since the integer division [N_{i-1}/q] just yields a constant which is multiplied with M .