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
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}$.
No comments:
Post a Comment