Solve a system of congruences using the Chinese Remainder Theorem

186 Views Asked by At

In an old group theory exam, I am asked to solve $\begin{cases}6x\equiv 3\mod 27 \\ 6x\equiv 2 \mod 10 \end{cases}$ $\color{purple}{\text{in }\mathbf{Z}/270\mathbf{Z}}$.

This question is asked right after a question where I am asked to find the kernel of the group homomorphism $\phi:\mathbf{Z}/270\mathbf{Z}\to \mathbf{Z}/270\mathbf{Z}:\overline{x}\mapsto\overline{6x}$.

In our syllabus, the only method outlined is the method to solve a system of congruences in the form $x=a_i \mod n_i$ for $i=1,2,\ldots$, so I have to turn my system of congruences into some system in the canonical form.

I did this in the following way, using some old topics on here: $$\begin{cases}6x\equiv 3\mod 27 \\ 6x\equiv 2 \mod 10 \end{cases} \iff \begin{cases}2x\equiv 1\mod 9 \\ 3x\equiv1\mod 5 \end{cases} \iff \begin{cases}x\equiv 5 \mod 9 \\ x\equiv 2\mod 5. \end{cases}$$

(If I understand correctly, we can always divide through a congruence by the common factor, i.e. $cx\equiv ca\mod cn \implies x\equiv a \mod n$ and we can divide through like this: $cx\equiv ca \mod n \implies x\equiv a\mod n$ if $\gcd(c,n)=1$.)

Now, using the Chinese Remainder Theorem algorithm, I get the answer $\color{red}{x=32\mod 45}$.

Is my method correct (also given that I need to solve this in $\mathbf{Z}/270\mathbf{Z}$)? Should I have used the question about the kernel in some way? Is there some easier way?

Could someone provide any help?

1

There are 1 best solutions below

2
On BEST ANSWER

Your solution is correct, the (unique) solution for $6x$ in $\mathbb{Z}/270\mathbb{Z}$ is $6x=6\cdot32=192$ because every solution is in $\{192+k\cdot\mathrm{lcm}(27,10)|k\in\mathbb{Z}\}$. For the solutions for $x$ you already found all six solutions by $x\equiv32\mod45$. Note you could arrive at this solution by observing that $x\equiv2^{-1} \mod 27$ and likewise $x\equiv3^{-1}\mod10$. The inverse elements in $\mathbb{Z}/n\mathbb{Z}$ can be found by the Euclidian algorithm, and thereafter you have a 'standard' system of congruences solvable by the CRT.

Using my method, you would have found $6x=192$ as the unique solution in $\mathbb{Z}/270\mathbb{Z}$ and than you should conclude that we have 6 solutions for $x$ (that is: $x\equiv32\mod45$. This makes sense since you found that the kernel of the group homomorphism in the previous question contains $6$ elements.