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

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

• 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!

• – lab bhattacharjee Nov 20 '17 at 5:41
• @R.C Your title is $\pmod {65}$ but your question is $\pmod {56}$. – Toby Mak Sep 1 '18 at 11:35

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

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