Explanation of this step in a modular arithmetic problem

Question

The multiplicative inverse of $5$ is $7$, when using mod $34$. $$\begin{align*} 5\cdot x&=3\\[0.1in] 7\cdot 5\cdot x &=7\cdot 3\\[0.1in] 1\cdot x &=7\cdot 3\\[0.1in] x&=21 \end{align*}$$

I don't understand this part:

$$\begin{align*} 7\cdot 5\cdot x &=7\cdot 3\\[0.1in] 1\cdot x &=7\cdot 3 \end{align*}$$

How is 7*5*x the same as 1*x?

Answer 1

Since $5x = 3 \pmod{34}$, you can multiply both sides of this equation by $7$ (the inverse of $5$ to obtain $7 \cdot 5x = 7 \cdot 3 \pmod{34}$. (The reason why this works is because $a=b \pmod{n}$ implies $ca = cb \pmod{n}$, and you should check this yourself if you haven't.)

Therefore since $$ 7 \cdot 5 = 35 = 34 + 1 = 0 + 1 = 1 \pmod{34}, $$ we obtain $$ x = 1 \cdot x = 7 \cdot 5 \cdot x = 7 \cdot 3 = 21 \pmod{34}. $$

Hope that helps,

Answer 2

Recall that $a\equiv b\bmod n$ precisely when $n$ divides the difference $a-b$. Therefore, we have $$35\equiv 1\bmod 34.$$ It is also true that if $a\equiv b \bmod n$, then $ac\equiv bc\bmod n$ for any $c$. Therefore, whatever $x$ is, $$35x\equiv x\bmod 34,$$ so that we can go from $$35x\equiv 21\bmod 34$$ to $$x\equiv 21\bmod 34.$$