2
$\begingroup$

I read a method to solve the linear congruence $$43x\equiv 12 \pmod{56}$$ indirectly from a book. The method is to find an equivalent system of congruences, and then solve the system to obtain a solution to the original linear congruence.

To solve $43x\equiv 12 \pmod{56}$, the book writes that it is equivalent to the system: $$x\equiv 5 \pmod{7}\qquad \text{and}\qquad 3x\equiv 4\pmod{8}.$$ Since every element in the group $(\mathbb{Z}/8\mathbb{Z})^*$ has order 2, $3x\equiv 4\pmod{8}$ is equivalent to $x\equiv 4 \pmod{8}$.

I have two questions about this equivalence.

  • First, how to obtain a system of congruences that is equivalent to the original linear congruence?

  • Second, why is $3x\equiv 4\pmod{8}$ equivalent to $x\equiv 4 \pmod{8}$ because the elements in $(\mathbb{Z}/8\mathbb{Z})^*$ have order 2?

Any help will be appreciated!

$\endgroup$
1
$\begingroup$

You can get an equivalent system from the facts that if

$$43x\equiv 12 \pmod{56}$$

then

$$56 | 43x-12 \implies 7(8)|43x-12$$

where $|$ means evenly divides. We use $7$ and $8$, since $56$ is the least common multiple of these divisors. So

$$7|43x-12$$

and

$$8|43x-12$$

Then, since $7|43x-12$, we have $7|42x+x-7-5$, so $7|x-5$ which gives $x\equiv 5 \pmod 7$. Also from $8|43x-12$ we have $8|40x+3x-8-4$, so $8|3x-4$, and then $3x\equiv 4 \pmod 8$. I do not know very much group theory, but I can answer your second question without group theory. Since $8|3x-4$, $8|3(3x-4)$, so $8|9x-12 \implies 8|8x+x-8-4 \implies 8|x-4$, so $x\equiv 4 \pmod 8$.

$\endgroup$
  • $\begingroup$ Oh, thanks! Your explanation is very clear and easy to understand! You give me a useful way to manipulate linear congruence. Thank you! $\endgroup$ – R.C Nov 20 '17 at 6:04

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.