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 57x1 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 x7(mod100). Thus every such x is of the form x=7+100t, where tZ.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...