# Why is my solution wrong to $\,99x \equiv 18 \mod 30$

ive had to solve $$\,99x \equiv 18 \mod 30$$

Firstly $$\gcd(99,30)=3$$ and $$3 | 18$$ so the equation has solutions.

I can devide by $$3$$. So we get:

$$33x \equiv 6 \mod 10$$

Since $$\,\gcd(33,10)=1$$ we can find an inverese to $$33$$ with the extended euclidean algorithm.

I calculated: $$(-3)33+10*10=1$$, so the inverse element should be $$-3$$

Now we write:

$$(-3)33x \equiv (-3)6 \mod 10$$

which should give:

$$x \equiv -18 \mod 10$$

So $$x=10*p + 8$$ with $$p\in \mathbb{Z}$$

But when I try out the found $$x$$ the solution is simply wrong..

Actually I found by trying out, $$x = 12$$ does work.. I am really confused where I messed it up :(

Can someone help? Thanks

• $( - 3)6 = -18$. However the rest are fine. Nov 16, 2020 at 14:32
• I am really sorry yeah it the german term :( gcd(a,b) ofc Nov 16, 2020 at 14:37
• But why isnt my solution working out.. when i choose for example $x=8$, then $99*8 \mod 30 \equiv 12 \mod 30$ Nov 16, 2020 at 14:39
• Your solution has a sign error. $-3\times 6=-18$ not $18$.
– lulu
Nov 16, 2020 at 14:44
• The error is in the last step. -18 is congruent to -8 or 2 mod 10. So x = 10*p + 2 Nov 16, 2020 at 14:46

Just reduce $$\pmod {30}$$ to $$9x \equiv 18 \pmod {30}$$ so that $$x=2$$ is a solution.
Even further, dividing by $$3$$ we get $$3x \equiv 6 \pmod {10}$$ to see that $$x\equiv 2 \pmod {10}$$ is the set of solutions.
Your solution isn't working because you have $$-99x \equiv -18 \pmod {10}$$ and to make this clear to you, add $$100x$$ to both sides so that $$x \equiv -18 \equiv 2 \pmod {10}$$. You could get to this instantly by noticing $$99 \equiv -1 \pmod {10}$$ as well.
• $x=2$ is far from the only solution. Nov 16, 2020 at 14:34
• $x=2$? What about the infinitely many other solutions? Perhaps you mean to say $x\equiv 2$... but then which $\equiv$ are you using here? $x\equiv 2\pmod{30}$? No. Nov 16, 2020 at 14:34
$$-18\equiv 2\bmod 10$$, not $$8$$.