2

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.

Martin Argerami
  • 205,756
dato datuashvili
  • 9,194

3 Answers3

1

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.

Student
  • 4,438
1

Yes, everything is correct. The solution is usually expressed with the smallest positive integer modulo 12, though, so it would be 8.

Martin Argerami
  • 205,756
1

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

zwim
  • 28,563