JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Tutorial Discussions Prime Numbers, Factorization and Euler Function Re: Modular division Revision History (1 edit)
Re: Modular division (response to post by dskloet)
Since M % x < x, (M - x * M/x) = M % x < x, so a decreases every iteration, and therefore the algorithm always terminates. It's probably slightly worse than an extended GCD, but I can type it from memory.

I'll usually pull out my code library and copy the EGCD if I have to solve a*x == b (mod m) with a, m possibly not coprime, though.
Re: Modular division (response to post by dskloet)
Since M % x < x, (M - x * M/x) = x % M < x, so a decreases every iteration, and therefore the algorithm always terminates. It's probably slightly worse than an extended GCD, but I can type it from memory.

I'll usually pull out my code library and copy the EGCD if I have to solve a*x == b (mod m) with a, m possibly not coprime, though.