modular arithmetic - Find all solutions; $17x equiv 25 (text{ mod } 33)$

Find all solutions $x \in \mathbb{Z}_{m}$ of the following congruence
whereby $m$ is the modulus. If there doesn't exist a solution, state
why.

$$17x \equiv 25 (\text{ mod } 33)$$

Alright so I have big trouble doing this because I only know how to do it if there was a $1$ instead of a $25$ on the right side : /

You then put all on one side and $33$ on the other side, use euclidean algorithm and calculate it. But what can I do in this case, when there isn't a $1$?

Is it done completely different or the same way?

Answer

Since $17$ and $33$ are coprime, i.e. $\gcd(17,33)=1$, we can find integers $m$ and $n$ for which $17m+33n=1$. We can find $m$ and $n$ by using the Extended Eulidean Algorithm.

We see that $m=2$ and $n=-1$, which gives $17\times 2 + 33 \times(-1)=1$. Reducing both sides modulo $33$ gives $17 \times 2 \equiv 1 \bmod 33$, i.e. $2$ is the multiplicative inverse of $17$, modulo $33$.

Coming back to $17x \equiv 25 \bmod 33$. If we multiply both sides by the multiplicative inverse of $17$, i.e. $2$, we get $34x \equiv 50 \bmod 33$, i.e. $1x \equiv 17 \bmod 33$. Hence $x = 33k+17$, where $k$ is an integer.