0
$\begingroup$

Find all solutions. You know that the multiplicative inverse is $2$.

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

First way of solving it:

Multiply this with $2$: $$34x \equiv 50(\text{mod } 33) $$

This is equivalent to:

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

So solution is $x = 33k+17$ where $k \in \mathbb{Z}$

Second way of solving it:

Multiply this with $2$: $$34x \equiv 50(\text{mod } 33) $$

$$50 \text { mod } 33= 17$$

Thus $x = 17$


My question, are both solutions correct? And if yes, which one would you recommend? The second seems more comfortable for sure.

$\endgroup$
  • 1
    $\begingroup$ The solutions are different, so how can they possibly both be correct? In particular, $x=17$ is just one solution, whereas you were asked to find all solutions. If there's more than one solution, your second answer must be wrong. $\endgroup$ – Gerry Myerson Feb 16 '17 at 11:05
  • $\begingroup$ @GerryMyerson Thank you now I understood, totally forgot the word "all" mentioned here. $\endgroup$ – cnmesr Feb 16 '17 at 11:08
1
$\begingroup$

The suggested solution might have been $$17x\equiv 25\pmod{33}$$

$$\iff 50x\equiv 25\pmod{33}$$

$$\stackrel{:25}\iff 2x\equiv 1\pmod{33}$$

(which we can do because $\gcd(25,33)=1$)

$$\iff x\equiv 2^{-1}\pmod{33}$$

$\endgroup$
1
$\begingroup$

$$17x \equiv 25 \pmod{33}$$

The "natural" thing to do with $17x \equiv 25 \pmod{33}$ is to multiply both sides by what is $\dfrac{1}{17} \pmod{33}$. Since $2\cdot17 \equiv 34 \equiv 1 \pmod{33}$, then $\dfrac{1}{17} \equiv 2 \pmod{33}$. Multiply both sides by $2$ and you get

\begin{align} 34x &\equiv 50 \pmod{33} \\ x &\equiv 17 \pmod{33} \\ x &= 17 + 33n \quad (n \in \mathbb Z) \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.