# Is a way to calculate faster x of this congruence

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

• Well, $20\equiv -3$ and $49\equiv 3$ so $x\equiv -1$.
– lulu
Feb 21, 2017 at 20:07
• 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... Feb 21, 2017 at 20:18
• Am I think correclty it is little tricky? Feb 21, 2017 at 20:28
• 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.
– lulu
Feb 21, 2017 at 20:32

• Cancelling $-3$ is valid because $-3$ is coprime to $23$ so invertible (by Bezout). Feb 21, 2017 at 20:23
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}$.