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?


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.

  • 2
    $\begingroup$ I think it's misleading to say that this gives a "unique solution in $\Bbb Z/270\Bbb Z$". There are six solutions in $\Bbb Z/270\Bbb Z$, namely $32,77,122,167,212,257\pmod{270}$, which are all congruent to $32\pmod{45}$ as the OP found. $\endgroup$ – Greg Martin Mar 26 '18 at 7:26
  • $\begingroup$ You're right, I'll edit to clear this up. $\endgroup$ – Václav Mordvinov Mar 26 '18 at 7:27

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.