1
$\begingroup$

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

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

2 Answers 2

Reset to default
3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ $x=2$ is far from the only solution. $\endgroup$
    – player3236
    Commented Nov 16, 2020 at 14:34
  • 1
    $\begingroup$ $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. $\endgroup$
    – JMoravitz
    Commented Nov 16, 2020 at 14:34
  • $\begingroup$ I swear I don't explain/write one thing well and get downvoted to oblivion, but some long answers I give to a few difficult questions either get closed or completely ignored. Not sure why this is the case. $\endgroup$
    – Derek Luna
    Commented Nov 16, 2020 at 14:52
2
$\begingroup$

$-18\equiv 2\bmod 10$, not $8$.

$\endgroup$

You must log in to answer this question.

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