-1

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.

AColoredReptile
  • 2,669
  • 10
  • 25
  • 1
    you could try the [extended Euclidean algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) to get a Bezout relation – J. W. Tanner Mar 18 '20 at 01:31
  • See [here](https://math.stackexchange.com/a/25395/242) and its links for *many* methods. – Bill Dubuque Mar 18 '20 at 01:41
  • See my post in https://math.stackexchange.com/questions/407478/solving-a-linear-congruence/407482 – lab bhattacharjee Mar 18 '20 at 01:42
  • 1
    $\bmod 43\!:\,\ \dfrac{1}{15}\equiv \dfrac{3}{45}\equiv \dfrac{46}{2}\equiv 23\ $ by [Gauss's algorithm](https://math.stackexchange.com/a/174687/242) and [modular halving](https://math.stackexchange.com/a/2326318/242). – Bill Dubuque Mar 18 '20 at 01:55

1 Answers1

1

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$

J. W. Tanner
  • 58,836
  • 3
  • 38
  • 78
  • This is essentially [Gauss's algorithm](https://math.stackexchange.com/a/3230/242) (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 01:46