MHB Parity equivalent to the system

[evinda]

Hello! (Mmm)

I have to write a parity that is equivalent to the system:$$\left\{\begin{matrix}
x \equiv 1 \pmod 4\\
x \equiv 2 \pmod 3
\end{matrix}\right.$$

That's what I tried:

$4,3$ are coprime.

We want to find a $c$,such that $x \equiv c \pmod {4 \cdot 3}$

We set $M=4 \cdot 3=12, M_1=3,M_2=4$

$$3x \equiv 1 \pmod 4$$
$$x \equiv 3 \pmod 4$$
$$\xi_1=3$$

$$4x \equiv 2 \pmod 3$$
$$x \equiv 2 \pmod 3$$
$$\xi_2=2$$

We set $c=M_1 \cdot \xi_1+M_2 \cdot \xi_2=17$

The system gets:

$$x \equiv 12 \pmod {12} \Rightarrow x \equiv 5 \pmod {12} \Rightarrow x=12q+5, q \in \mathbb{Z} $$

Could you tell me if it is right? (Thinking)

 

[I like Serena]

Hi! (Blush)

Well... the final answer is correct... but the way to it doesn't look very pretty. (Wait)First it seems you're mixing up $x$ and $\xi_1$ respectively $x$ and $\xi_2$.

And then you got $x \equiv 12 \pmod {12}$, which is not correct. (Doh)

 

[evinda]

Hi! (Blush)

Well... the final answer is correct... but the way to it doesn't look very pretty. (Wait)First it seems you're mixing up $x$ and $\xi_1$ respectively $x$ and $\xi_2$.

And then you got $x \equiv 12 \pmod {12}$, which is not correct. (Doh)

So,is the way I solved the exercise wrong?? (Sweating)

Oh,sorry! I wanted to write $x \equiv 17 \pmod {12} \Rightarrow x \equiv 5 \pmod {12}$..

 

[I like Serena]

So,is the way I solved the exercise wrong?? (Sweating)

The method is correct.

Oh,sorry! I wanted to write $x \equiv 17 \pmod {12} \Rightarrow x \equiv 5 \pmod {12}$..

Ahaa ;)

 

[evinda]

The method is correct.

Ahaa ;)

Have I done also an other mistake,except from writing $x \equiv 12 \pmod{12}$ ? (Thinking)

 

[I like Serena]

Have I done also an other mistake,except from writing $x \equiv 12 \pmod{12}$ ? (Thinking)

Nope. No other mistakes. ;)

It's just that the line of reasoning is hard to follow.
It requires thorough knowledge of the method to make sense of it.

 

[evinda]

Nope. No other mistakes. ;)

It's just that the line of reasoning is hard to follow.
It requires thorough knowledge of the method to make sense of it.

A ok... Thank you very much! (Whew)

 

[Deveno]

Just an aside, what you are doing is applying the Chinese Remainder Theorem.

If we consider the rings $\Bbb Z_m$ and $\Bbb Z_n$, we can form the ring:

$\Bbb Z_m \times Z_n$ by adding and multiplying pairs $(a,b)$ "one coordinate at a time":

$(a,b) + (a',b') = (a+a'b+b')$
$(a,b)\cdot(a',b') = (aa',bb')$ where the operation in the first coordinate is mod $m$, and the second coordinate mod $n$.

Now, if gcd($m,n$) = 1, it is not hard to see that $(1,1)$ has (additive) order $mn$, so that we obtain a ring isomorphism:

$\Bbb Z_{mn} \to \Bbb Z_m \times \Bbb Z_n$, given by:

$[k]_{mn} \mapsto ([k]_m,[k]_n)$.

Solving a congruence:

$x \equiv a\text{ (mod }m)$
$x \equiv b\text{ (mod }n)$

where gcd($m,n$) = 1 is thus equivalent to finding the "inverse isomorphism" of the one above:

trying to find $([k]_{mn})$ such that $[k]_m = [a]_m$ and $[k]_n = _n$.

So let's look at such pairs $([a]_m,_n)$ (I will drop the brackets at times, with the understanding that the first element is mod $m$, the second element is mod $n$).

Note we can write $(a,b) = a(1,0) + b(0,1)$, so what we really want to know is: where do (1,0) and (0,1) wind up under the inverse isomorphism?

Note that (1,0) has order $m$, so it must map to an element of order $m$ in $\Bbb Z_{mn}$. Now if:

$mc = dmn$, it is clear that $c$ is a multiple of $n$, Similarly, (0,1) must map to some multiple of $m$.

So, let's look at what happens to $[dn]_{mn}$ in our original isomorphism. It gets sent to $([dn]_m,[0]_n)$. This means we want to find $d$ such that:

$dn = 1\text{ (mod }m)$

Since gcd($m,n$) = 1, $[n]_m$ is invertible, that is: we should choose $[d]_m = [n^{-1}]_m$.

The same logic shows that the element $[d'm]_{mn}$ that is the pre-image of (0,1) is $m[m^{-1}]_m$.

So what we are looking for as the pre-image of $(a,b)$ is:

$[an[n^{-1}]_m + bm[m^{-1}]_n]_{mn}$

Does this work? Let's try it out on our sample problem here: we have a = 1, b = 2, m = 4, n = 3.

First, we find the inverse of 3 mod 4. It is easy to see that this is 3 itself (3*3 = 9 = 2*4 + 1).

So $an[n^{-1}]_m = 1*3*3 = 9$.

Next, we find the inverse of 4 mod 3, which is 1 (4 = 1 mod 3, and is its own inverse).

So $bm[m^{-1}]_n = 2*4*1 = 8$.

Finally, we add the two, and reduce mod 12, to get 17 = 5 (mod 12). Hey, it works!