# Understanding modular arirthmetic

As part of a proof of the CRT, I've encountered the following:

We want to find a solution for the system

$$x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2}$$

Then the author look for a solution of the form $x= a_1 +dy$ and claims that the system is equivalent to:

$$dy \equiv 0 \pmod{n_1} \\ dy \equiv a_2 - a_1 \pmod{n_2}$$

In the second equation it seems like he was able to "move" the $a_1$ term to the other side of the equivalence - Why is it valid?

• Do you mean $x = a_1 + dy$?
– orlp
Dec 1 '17 at 22:24
• @orlp, yes let me correct that Dec 1 '17 at 22:24
• @Elimination Just a latex/mathjax comment. Use \pmod to write $\mod{}$ in brackets. Dec 1 '17 at 22:30
• @MathLover, noted thanks! Dec 1 '17 at 22:31

Note that $a \equiv b \pmod n \iff (a-c) \equiv (b-c) \pmod n$. This relation is true as:

$$a \equiv b \pmod n \iff n \mid a-b \iff n \mid (a-c) - (b-c) \iff (a-c) \equiv (b-c) \pmod n$$

• Can you explain how is $c$ getting into the picture in the second line? (second iff) Dec 1 '17 at 22:30
• @Elimination It was a typo. We have $a-b = (a-c) - (b-c)$, right? Dec 1 '17 at 22:34
• I see. Thanks! (it also needs to be fixed in the later iff + the first line) Dec 1 '17 at 22:41
• @Elimination Done! Dec 1 '17 at 22:42

Substitute $x= a_1 +dy$ into both equations:

$$a_1 +dy \equiv a_1 \mod n_1$$ $$a_1 +dy \equiv a_2 \mod n_2$$

And subtract $a_1$ from both sides in both equations:

$$dy \equiv 0 \mod n_1$$ $$dy \equiv a_2 - a_1 \mod n_2$$

In modular arithmetic just like ordinary arithmetic you're allowed to add, subtract or multiply both sides of an equivalence by the same number.