$4x≡2\mod5$ can you divide both sides by $2$ to get $2x≡1\mod5\,?$

Since gcd$(2,5)=1$ , could you treat $4x$ as $2(2x)$ and cancel the $2$ on both sides? i.e. $$2(2x)≡2\mod5\implies 2x≡1\mod5$$

Thanks!

Solution 1:

In short , Yes you can$^1$ .

$$4x\equiv 2\mod5 \implies 4x -2 = 5\lambda$$

Notice that L.H.S is divisible by $2$ , which implies that R.H.S must also be divisible by $2$ or $\lambda = 2\alpha$. So our equation becomes :

$$2(2x-1) = 5\cdot2\alpha\implies 2x-1\equiv \mod 5 \implies \color{#4d0}{2x \equiv 1\mod5}$$

$(1.)$ Note that in $ax \equiv b \mod c$ , if G.C.D$(a,b) = k$ , such that $k\mid c$ then :

$$ax\equiv b \mod c \implies \color {#c03}{\frac ak \equiv \frac bk \mod \frac ck}$$

For example , consider $4x \equiv 2 \mod 6$ , this equivalent to

$$4x\equiv 2\mod 6 \implies 2(2x-1) = 6\lambda$$ $$(2x-1) = 3\lambda \implies \color{#d0d}{2x\equiv 1 \mod 3}$$

Solution 2:

THEOREM $1$. If

• $ax \equiv b \pmod n$
• $d \mid a$ and $d \mid b$
• $\gcd(d,n)=1$

then $\dfrac adx \equiv \dfrac bd \pmod n$

PROOF.

If $d \mid a$ and $d \mid b$, then there exists integers, $A$ and $B$, such that $a = dA$ and $b =dB$.

If $\gcd(d,n)=1$, then there exists integers, D and E, such that $Dd + nE = 1$. It follows that $Dd \equiv 1 \pmod n$.

So \begin{align} ax \equiv b \pmod n &\implies dAx \equiv dB \pmod n \\ &\implies DdAx \equiv DdB \pmod n \\ &\implies Ax \equiv B \pmod n \\ &\implies \dfrac adx \equiv \dfrac bd \pmod n \end{align}

Using the same sort of reasoning, we can also prove

THEOREM $2$. If

• $ax \equiv b \pmod n$
• $d \mid a$, $\ d\mid b$, and $d \mid n$

then $\dfrac adx \equiv \dfrac bd \left( \mathrm{mod} \ \dfrac nd \right)$

Solution 3:

Here is a somewhat more conceptual way to think about @stevengregory 's correct answer.

Since $2$ and the modulus $5$ are relatively prime, $2$ has a multiplicative inverse $d \pmod{5}$. ($d$ happens to be $3$, but its value is irrelevant in this argument.) Then multiplying both sides of the congruence $$ 4x \equiv 2 \pmod{5} $$ by $d$ gives $$ d \times 2 \times 2x \equiv d \times 2 \pmod{5} . $$ But $d \times 2 \equiv 1 \pmod{5}$ (that's what "multiplicative inverse" means) and the result you want follows.

In general, it's better to think about multiplication by inverses rather than division when working with congruences.

Solution 4:

Hint $ $ Scaling an equation by an element that is cancellable (e.g. a unit = invertible) always yields an $\rm\color{#c00}{equivalent}$ equation - see below. In your case $\bmod 5\!:\ a\equiv 2\,$ is a unit by $\,2\cdot 3\equiv 1$. Recall, by Bezout: $\,a\,$ is a unit $\!\bmod n\!\iff\! \gcd(a,n) = 1$.

Lemma $\ \,ax\equiv b\iff x\equiv a^{-1}b\ $ when $\,a\,$ is a unit (invertible) $\ \ $ [Unit Scaling $\rm\color{#c00}{Equivalence}$]

$\begin{align}{\bf Proof}\ \ (\Rightarrow)\ \ \ ax&\equiv b\, \overset{\large \times\ a^{-1}\!}\Longrightarrow\, x\equiv a^{-1}b,\ \ \text{i.e. cancel $\,a\,$ by scaling by $\,a^{-1}$}\\ (\Leftarrow)\ \ \ ax&\equiv b\, \overset{\large \times\ a}\Longleftarrow\,\ x\equiv a^{-1}b,\ \ \text{i.e. scale by}\,\ a\ \ \text{(= inverse of scaling by $\,a^{-1}$)} \end{align}$

In both inferences above we applied the Congruence Product Rule.

Solution 5:

Yes, exactly. $4x \equiv 2 \mod5 \implies 4x - 2 = 5k \implies 2(2x-1)=5k \implies 5$ divides $2x-1$ as $\gcd(2,5)=1 \implies 2x \equiv 1 \pmod5$

Note: please feel free to edit this answer.