2
$\begingroup$

This is from a youtube video on the Chinese Remainder Theorem - https://www.youtube.com/watch?v=ru7mWZJlRQg

enter image description here

What the author has done thus far is basically
1.Make sure that the mods, 3, 4, 5 are relatively pairwise prime by showing that gcd(3,4) = 1, gcd(3,5) = 1 and gcd(4,5) = 1.
2.Set up a table with mod 3, mod 4, mod 5 as the columns. He multiplied one column by the other two so that when applied it's modulus, say for mod 3, mod 4 and mod 5 column values will be set to zero.
3.Here's the part that I have a question about. The author states that the first linear congruence
x $\equiv$ 2(mod 3) must be satisfied and to do so, he mods all the values by 3. The only non zero value will be the value in column 1(because of the last step).
My question is by the definition of a is congruent to b modulo m(below) enter image description here

Shouldn't the author have to subtract all the values by 2 first and then mod 3, that way he get 18 mod 3, 13 mod 3, and 9 mod 3, or 0, 1, and 0? Is there a reason he doesn't have to do this? To me, this isn't consistent with the definition of congruency

$\endgroup$
  • $\begingroup$ Are you saying that $x=20mod3$ is the set of solutions to all three equations? $\endgroup$ – imranfat Feb 13 '15 at 18:09
  • $\begingroup$ ${\rm mod}\ 3\!:\ 15\equiv 0 \equiv 12\,\Rightarrow\, n+15+12\equiv n\,$ by the Congruence Sum Rule. The point is, that by construction, all the other columns are $\equiv 0\pmod 3.\ $ $\endgroup$ – Bill Dubuque Feb 13 '15 at 18:12
  • $\begingroup$ Not me, its the video. What he first did to satisfy the first congruence, x ≡ 2 mod( 3) , was to apply mod 3 to all three columns. He was left with 20, 0, 0, meaning x = 20 mod (3) or x$\equiv$ 20 mod(3) which is equivalent to x $\equiv$ 2 mod (3) $\endgroup$ – committedandroider Feb 13 '15 at 18:12
  • $\begingroup$ @BillDubuque At the bottom of that snippet, shouldn't it be x≡ 20 mod(3), not x = 20 mod (3)? I don't think by definition, they mean the same thing? $\endgroup$ – committedandroider Feb 13 '15 at 18:14
  • $\begingroup$ $\,x\equiv 20\equiv 2\pmod3\,$ so it is a solution of the first congruence, as claimed. $\endgroup$ – Bill Dubuque Feb 13 '15 at 18:16
1
$\begingroup$

First that's not the only definition there is of congruence. For example you may define it as :

Two integers $a$ and $b$ are said to be congruents modulo m if the remainders of the division of $a$ and $b$ by $m$ are equal.

Which is equivalent to your definition, and for some more intuitive.

Second, notice that congruence is an equivalence relation and also we may sum and multiply through congruence.

Third you may represent a residue class by

$$ \overline {a} = \{x \in \mathbb Z ; x \equiv a \mod m\} $$

and the basic properties of arithmetic you are used to with the integers is also valid here. With this in mind we may "apply" congruence modulo $3$ to obtain

$$\overline{x} = \overline {20 + 15 + 12} = \overline {20} + \overline {15} + \overline {12} = \overline {2} + \overline {0} + \overline {0}$$

Because according to definition we gave here $$20 = 6 \cdot 3 + \color{#f05}2\ ,\ 15 = 5 \cdot 3 + \color{#f05}0\ ,\ 12 = 4 \cdot 3 + \color{#f05}0\ \ \text{and}\ \ 2 = 0 \cdot 3 + \color{#f05}2$$

In order words, $$ x \equiv 20 \equiv 2 \mod 3$$

Also you may notice that, of course,

$$(20 -2) \equiv 0 \mod 3$$

Because $$18 = 6 \cdot 3 + \color{#f05} 0$$

$\endgroup$
  • $\begingroup$ Feel free to ask if you have any questions. $\endgroup$ – Aaron Maroja Feb 13 '15 at 18:59
  • $\begingroup$ Is a residue class the same as a set? I noticed that you used set builder notation. $\endgroup$ – committedandroider Feb 13 '15 at 23:33
  • $\begingroup$ Yes it is, think of $\mathbb Z_2 = \{\overline{0}, \overline{1}\}$. The subset $\overline{1}$ for instance, is the one that contains all odd numbers. $\endgroup$ – Aaron Maroja Feb 13 '15 at 23:36
  • $\begingroup$ SO because congruence is an equivalence relation, you are basically summing $\equiv$20mod(3) + $\equiv$15mod(3) + $\equiv$12mod(3) and getting $\equiv$2mod(3) as the final answer? $\endgroup$ – committedandroider Feb 13 '15 at 23:39
  • $\begingroup$ That's right!.. $\endgroup$ – Aaron Maroja Feb 13 '15 at 23:42

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.