checking of understanding solution of linear congruent equation Let us consider following equation
$${30x}\equiv 24\pmod {72}.$$
I would like to  understand steps of  solving such equation, first of all let us find GCD of  two number  $30$ and  $72$
$$d=gcd(30,72)=6. $$
after that we can write  like this
$$30=r\times d$$
from which  $r=5$.
$$24=6s$$
so we have  $s=4$
and
$$72=6n. $$ 
After solving for $n$, we have  $n=12$, 
so that  original equation is equivalent to 
$${5x}\equiv 4\pmod {12}. $$
Now  let us find inverse  of  $5$ with modulus $12$, such number is $5$, because
$${5\times5}\equiv 1\pmod {12}.$$
So  after multiplication by $5$, we will get
$${x}\equiv 20 \pmod {12}. $$
Am I right? Thanks in advance. 
 A: First of all: your solution is completely correct. However, you could have shortened the step where you go from $30x \equiv 24 \mod 72$ to $5x \equiv 4 \mod 12$. 
Because of the definition of $\mod n$, you know that $a \equiv b \mod n$ if and only if $a = b + kn$ for some $k \in \mathbb{Z}$. Hence you have that 
$$a - b = kn$$
which is equivalent with stating that $n$ divides $(a-b)$. 
Now we have that $30x - 24 = 72k$ for some $k \in \mathbb{Z}$. Since $6$ divides $30, 24, 72$, you have that $5x -4 = 12k$ (for the same $k$). Hence it follows that $5x \equiv 4 \mod 12$.
In a nutshell: you can always divide $a \equiv b \mod n$ by $\text{gcd}(a,b,n)$ to find an equivalent congruence.
A: Yes, everything is correct. The solution is usually expressed with the smallest positive integer modulo 12, though, so it would be 8.
A: Since you seem to be new to congruence, I think it is important also to show you some pitfalls.
What is wrong in the following ?
$\begin{array}{lll}
30x\equiv 24 \pmod{72} & \mathrm{multiplying\ by\ }3 & \Rightarrow\\
90x\equiv 72 \pmod{72} & \mathrm{simplifying\ }72\equiv0\ \mathrm{and\  }72x\equiv0 & \Rightarrow\\
18x\equiv 0 \pmod{72} & \mathrm{dividing\ by\ }18 & \Rightarrow\\
x\equiv 0 \pmod{4}\\
\end{array}$
Note that you obtained $x\equiv 8\pmod{12}$, so $x=12n+8$ is effectively a multiple of $4$, but we have lost some information in the way.
In fact the implications are true, but the mutiplication by $3$ is not an equivalence.
In the same way if you start from $5x\equiv 4\pmod{12}$ and multiply by $4$ for instance you get $20x\equiv 8x\equiv 16\equiv 4\pmod{12}$ and divide back by $4$ you end up with $2x\equiv 1\pmod{3}$ or equivalently $x\equiv 2\pmod{3}$.
This is not false, but you lost information in the way. You can verify that $x=12n+8=3(4n+1)+2$ so $x\equiv 2\pmod{3}$ makes sense.

From $ax=b\pmod{m}$ in order to keep the equivalence, you are allowed ($k$ is an integer) :


*

*to add or substract $c$ from each side

*to replace $-c$ by $m-c$ (or any $km-c$)

*to replace any $km$ or any $(km)x$ by $0$

*to multiply the equation by $\bar{a}=a^{-1}$ i.e. $a\bar{a}\equiv 1\pmod{m}$

*to divide the whole equation (that is $a,b$ and $m$) by $\gcd(a,b,m)$

*to multiply $a$ and $b$ by $n$ and keep $\pmod{m}$ only when $\gcd(m,n)=1$

*to divide $a$ and $b$ by $n=\gcd(a,b)$ and keep $\pmod{m}$ only when $\gcd(m,n)=1$


So for instance you can do things like this $(a+b)^3\equiv a^3+b^3\pmod{3}$ because other factors $3a^2b, 3ab^2$ are divisible by $3$.
If you have a doubt about something do not hesitate to get back to the definition, which is $\exists k\in\mathbb N\mid ax=mk+b$ and work your way from there.

I think the most important thing to remember in order to keep equivalences is to avoid multiplications and divisions with numbers that have common factors with the modulo $m$.

