# Solve $660x\equiv 1$ mod $43$ [duplicate]

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.

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$$

• 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). – Bill Dubuque Mar 18 '20 at 1:46