2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hint: Any two inverses will be congruent mod $100$. $\endgroup$ – Tobias Kildetoft Apr 27 '15 at 17:55
  • $\begingroup$ Hint 93 = 100-7 $\endgroup$ – Surb Apr 27 '15 at 17:56
  • $\begingroup$ you can write $\frac{1}{57} and adding or subtracting 100 to the numerator until we get a integer number $\endgroup$ – Dr. Sonnhard Graubner Apr 27 '15 at 17:59
0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ errrm... $\bmod 100$ cough $\endgroup$ – AlexR Apr 27 '15 at 17:57
  • $\begingroup$ @AlexR thanks for pointing the typo. $\endgroup$ – Anurag A Apr 27 '15 at 17:58
  • $\begingroup$ Man that was really simple. I feel dumb now haha. Thanks for the help. $\endgroup$ – Avernikas Apr 27 '15 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.