Parity check and magnitude comparison in Residue Number Systems
The "parity check" of a number $X$ is 0 or 1 according to whether $X$ is even or odd.  In other words, the parity of $X$ is $X \bmod 2$.  We are assuming that you have a way to compute the parity of $X$, from the RNS representation of $X$.  Let $p(X)$ denote the parity of $X$, i.e., $p(X) = X \bmod 2$.

Now let's suppose $X,Y$ are integers in $[0,M-1]$ that we have stored in RNS representation, and let's look at what happens when we subtract the RNS representations.  If $X$ is represented as $(x_1,\dots,x_t)$ and $Y$ is represented as $(y_1,\dots,y_t)$, the result of the subtraction operation will be the RNS representation $(z_1,\dots,z_t)$ where $z_i = x_i-y_i \bmod m_i$.

What number $Z$ is $(z_1,\dots,z_t)$ the representation of?  Well, if $X\ge Y$, then $Z$ will be $X-Y$.  But -- and here is the key point -- if $X&lt;Y$, then $Z$ will not be $X-Y$, as $X-Y$ is negative and RNS can only represent numbers in the range $[0,M-1]$.  Instead, what will happen is that we'll have $Z \equiv X-Y \pmod M$.  Therefore, if $X&lt;Y$, we'll have $Z = X-Y+M$... which is not the same as $X-Y$.

If $X\ge Y$, then $X-Y \ge 0$ and we say that the subtraction $X-Y$ doesn't underflow; in this case, $p(Z)$ will be $p(X)$ minus $p(Y)$ modulo 2.  In other words, if $X \ge Y$, we will have $Z=X-Y$ and therefore using the properties of modulo-2 arithmetic we have

$$p(Z) = p(X-Y) \equiv X-Y \equiv p(X)-p(Y) \pmod 2.$$

In contrast, if $X &lt; Y$, then $X-Y &lt; 0$ and we say that the subtraction $X-Y$ underflows.  In this case, $p(Z)$ will be $p(X)$ minus $p(Y)$ plus 1 modulo 2.  In other words, if $X&lt;Y$, we will have $Z=X-Y+M$ and therefore

$$p(Z) = p(X-Y+M) \equiv X-Y+M \equiv p(X)-p(Y)+1 \pmod 2.$$

Here I have used the fact that $M$ will always be odd, so $p(M)=1$.



This gives you a way to check whether $X\le Y$, given RNS representations for $X,Y$: you subtract them to get a RNS representation of some integer $Z$, and then test whether $p(Z) \stackrel{?}{\equiv} p(X)-p(Y) \pmod 2$.

The key observation is that "subtraction" of RNS representations is not actually computing the subtraction (of integers).   Rather, it is computing the subtraction modulo $M$.  If the result of the subtraction is in the range $[0,M-1]$, that's equivalent to subtraction in the integers.  But if subtraction underflows, it's different.

This might look mysterious, but it's not as unfamiliar as it might feel.  If you use twos-complement arithmetic on 32-bit integers, that is basically doing modulo $2^{32}$ arithmetic: addition of 32-bit ints is not actually addition (of integers), but addition modulo $2^{32}$.  In other words, with twos-complement addition of 32-bit integers, the results of arithmetic operations "wrap around" modulo $2^{32}$.  RNS is just like that, except that it "wraps around" modulo $M$ instead of modulo $2^{32}$.



"parity is off" means "parity is wrong", i.e., the parity doesn't match what you'd expect to get, if subtraction of RNS representations behaved like subtraction of integers.