Wednesday, June 15, 2016

discrete mathematics - Why doesn't the author subtract everything by two first before applying modulus?



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


Answer



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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...