0
$\begingroup$

We have $20x \equiv 49 \ (mod \ 23)$

and I noticed after multiplying $20*22$ or increasing $49$ by $23$ to $440$ emoticon:|. Is there a faster way to calculate x?

Solution $x$ is $22$

Notice I must calculated this by hand

$\endgroup$
4
  • 4
    $\begingroup$ Well, $20\equiv -3$ and $49\equiv 3$ so $x\equiv -1$. $\endgroup$
    – lulu
    Feb 21, 2017 at 20:07
  • $\begingroup$ ah instead of reduce by 'one number' 23 in case 20 and reduce few times in case 49 I increased 49 by 23 to 440... $\endgroup$
    – Grisza
    Feb 21, 2017 at 20:18
  • $\begingroup$ Am I think correclty it is little tricky? $\endgroup$
    – Grisza
    Feb 21, 2017 at 20:28
  • $\begingroup$ Not sure I get what you are asking. I don't understand your method, but you got the right answer! After all, $22\equiv -1\pmod {23}$ we our results match. I think my method is easier, but yours appears to have worked. $\endgroup$
    – lulu
    Feb 21, 2017 at 20:32

2 Answers 2

5
$\begingroup$

\begin{align*} 20x &\equiv 49 &\pmod{23} \\ -3x &\equiv 3 &\pmod{23} \\ x &\equiv -1 &\pmod{23} \\ &\equiv 22 &\pmod{23} \end{align*}

$\endgroup$
2
  • 2
    $\begingroup$ Cancelling $-3$ is valid because $-3$ is coprime to $23$ so invertible (by Bezout). $\endgroup$ Feb 21, 2017 at 20:23
  • $\begingroup$ Yes. Please note @BillDubuque 's comment. $\endgroup$ Feb 21, 2017 at 20:34
0
$\begingroup$

For this specific case, of course it is easiest to notice that $20\equiv -3$ and $49 \equiv +3$, as in the comments.

In the general case, it is useful to first apply Euclid's algorithm on the multiplier of $x$ (here, $23$ and the modulus. So let's say we needed to solve $23x=2\pmod {79}$; we would have $$ 79 = 3(23)+10\\23 = 2(10)+3\\10=3(3)+1 $$ and then $$ 1 = 10 - 3(3) = 10-3(23-2(10))\\ = 7(10)-3(23) = 7(79-3(23))-3(23) \\= 7(79) - 24(23) \equiv -24(23) $$ So $$24(23) \equiv -1 \pmod{79}$$ and $x = 24(-2) \equiv 31 \pmod{79}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .