-1
$\begingroup$

Solve $660x\equiv 1$ mod $43$

I found $660\equiv 15$ mod $43$

So I want to solve $15x\equiv 1$ mod $43$

I tried some low numbers but none of them worked. I'm not sure what to do now.

$\endgroup$
4
1
$\begingroup$

Here's one way:

$15\times3=45\equiv2\bmod 43$

$2\times 22=44\equiv 1\bmod 43$

Therefore

$15\times 3\times22\equiv 1 \bmod 43$

$15\times 66\equiv1\bmod 43$

$15\times 23\equiv 1 \bmod 43$

$\endgroup$
1
  • $\begingroup$ This is essentially Gauss's algorithm (in non-fractional form). Follow the link in case it is not clear from above how it works generally (for prime moduli only). $\endgroup$ – Bill Dubuque Mar 18 '20 at 1:46

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