Monday, December 11, 2017

modular arithmetic - Finding possible inverses of a modulo function



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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...