Property of modular arithmetic. $a \bmod p = b \bmod p \iff p \uparrow |a-b|$

Question

As I am doing revision, I stumble upon a proof in one of my computer science books (sparse with proofs). At one point they mention that to compute the equality of bit strings, then they check if $$a \bmod p = b \bmod p$$ and states that this is only true if $p$ divides $|a-b|$, which they denote as $$p \uparrow |a - b|.$$

Note that $p$ is a prime.

Why is this?

Answer 1

I think the binary operation of "mod" in the OP refers to the remainder.

Let $a=q_1 p + r_1$ and $b=q_2 p + r_2$, where $0\le r_1,r_2<p$. Then $$r_1=(a \bmod p),\ r_2=(b\bmod p).$$

If $\,a \bmod p\, =\, b \bmod p,\,$ i.e. $\,r_1=r_2,\,$ then $$|a-b|=|q_1 p + r_1-(q_2 p + r_2)|=|(q_1-q_2)p|=|q_1-q_2|p.$$ So $p \mid |a-b|$.

Conversely, if $\,p \mid |a-b|\,$ then $\,a\bmod p =b \bmod p$. I leave this part for you.