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

Question

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 1

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.

Answer 2

If you know how to solve $17y \equiv 1 \bmod 33$, then $x=25y$ is a solution of $17x \equiv 25 \bmod 33$.

Answer 3

$$17x = 25 \pmod {33} \iff 16 x = 8 \pmod {33} \iff 2x = 1 \pmod {33}$$

Where the last comes from the fact that $8 \land 33 = 1$ (so we can "divide both sides" by $8$).

Therefore $x = 2^{-1} = 17 \pmod {33}$.

Answer 4

Comment: You need to recall that ax ≡ b (mod n) has a solution if and only if gcd(a, n) is a divisor of b. Also note that the congruence is stated modulo 33, and so the most satisfying answer is given in terms of congruence classes modulo 33. Solution: We have gcd(17, 33) = 1, so there is a solution since 1 is a factor of 25. Solving the congruence 17x ≡ 25 (mod 33) is equivalent to solving the equation 17x = 25+ 33q for integers x and q. We next use trial and error to look for the multiplicative inverse of 17 modulo 33. The numbers congruent to 1 modulo 33 are 34, 67, 100, 133, etc., and −32, −65, −98, etc. Among these, we see that 17 is a factor of 34, so we multiply both sides of the congruence by 2 since (2)(17) = 34 ≡ 1 (mod 33). Thus we have 34x ≡50 (mod 33), or x ≡ 17 (mod 33). The solution is x ≡ 17 (mod 33).

Answer 5

Since $17$ is coprime to $33$ we can use the extended Euclidean algorithm to obtain $17j+33k = 1,\,$ so ${\rm mod}\ 33\!:\ 17j\equiv 1,\,$ i.e. $\,j\equiv 17^{-1}.\,$ To solve $\,17x\equiv 25\,$ multiply both sides by $\,17^{-1}\equiv j,\,$ yielding $\, x\equiv 25j.\,$ Doing so we get $\, 17(2)-33(1) = 1\,$ so $\,17^{-1}\equiv j\equiv 2\ $ so $\ x\equiv 25(2)\equiv 17.$

---

Or we can use Gauss's algorithm, which scales the (top & bottom) of a modular fraction to make the bottom smaller when reduced mod $33$, e.g. $\,2\cdot \color{#0a0}{17}\equiv 34\equiv\color{#c00}{\bf 1} < \color{#0a0}{17}\,$ below.

$$ {\rm mod}\ 33\!:\,\ x\equiv \color{}{\dfrac{25}{\color{#0a0}{17}}}\equiv \dfrac{50}{34}\equiv \dfrac{17}{\color{#c00}{\bf 1}}$$

Beware $ $ Modular fraction arithmetic is valid only for fractions with denominator coprime to the modulus. See here for further discussion.