JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums 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.