I'm working through some modular arithmetic for cryptography. I have a (probably simple) proof that I want to work through. The problem is this:
Prove that
$$(-a)\text{ mod }m = m - (a \text{ mod }m)$$
My instinct is to separate the -1 and a like this:
$$(-a)\text{ mod }m = ((-1) \text{ mod }m)*(a \text{ mod }m)$$
I then wrote $a$ and $-1$ as: $$-1 = m*q_1 + r_1$$ $$a = m*q_2+r_2$$
By substituting the values in I get a polynomial like:
$$(-a)\text{ mod } m = (m*q_1*m*q_2+m*q_1*r_2 +r_1*m*q_2 +r_1*r_2) \text{ mod } m$$ then factoring out $m$ gives $$(-a)\text{ mod } m = (m*(q_1*m*q_2+q_1*r_2 +r_1*q_2) +r_1*r_2) \text{ mod } m$$ I then jump to (this seems like some missing steps) $$(-a)\text{ mod } m = (r_1*r_2) \text{ mod } m$$
I don't seem to be getting where I need to be with this. It looks like I'm missing some steps or maybe not thinking this through correctly.
Can anyone give me a hint on how this might be done?
What is your definition of $c \bmod m$? One version is to use the division algorithm to write $c=qm+d$ where $d \in [0,m-1]$ Then if $a \bmod m=b$ you have $-a=-qm-b=-(q-1)m+(m-b)$ where $m-b \in [0,m-1]$