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?
Best 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.