Finding possible inverses of a modulo function

190 Views Asked by At

I know how to find $one$ inverse via the euclidean algorithm, but I can't figure out how to find more of them.

For example:

Find an inverse $x$, of $57$ $modulo$ $100$ Or an $x$ such that $57x ≡ 1$ modulo 100

I got the answer $-7$ from the euclidean algorithm, but then the domain of x is restricted to be between $0$ and $100$. I know $93$ works, but not how I would go about finding that on paper.

Thanks

1

There are 1 best solutions below

3
On BEST ANSWER

Once you get one answer $x=-7$ then all the others can be obtained by using the fact that $x \equiv -7 \pmod{100}$. Thus every such $x$ is of the form $x=-7+100t$, where $t\in \mathbb{Z}$.