1
$\begingroup$

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?

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

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$$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.