I was teaching Discrete this semester and set the students loose on a system of linear congruences. One of them came up with this solution. Say $$ x \equiv 1 \textrm{ mod } 3 $$ $$ x \equiv 3 \textrm{ mod 4} $$ $$ x \equiv 2 \textrm{ mod } 5. $$

Then, we convert each congruence to a mod 60 congruence: $$ 20x \equiv 20 \textrm{ mod } 60 $$ $$ 15x \equiv 45 \textrm{ mod } 60$$ $$ 12x \equiv 24 \textrm{ mod } 60 $$ and sum them to get a single congruence $$ 47x \equiv 89 \textrm{ mod } 60.$$ The coefficient on the left will always be relatively prime to the mod, so this method always works.

This has to have been seen and studied before, right? I'm curious about the time complexity relative to the "standard" methods since we only have to calculate one multiplicative inverse. I imagine this is a loser on space complexity since that inverse is happening with the large modulus rather than the small ones. Any pointers to other discussions of this solution method, particularly complexity-wise?


1 Answer 1


If you're using the (extended) Euclidean algorithm to compute modular inverses mod $m$, then the time complexity is roughly $O((\log m)^2)$. So if $m = abc$ then you'd prefer to do $(\log a)^2 + (\log b)^2 + (\log c)^2$ work rather than $(\log a + \log b + \log c)^2$ work. In fact, it's a general rule of thumb in computational number theory that if the factorization is available, and you can apply the Chinese remainder theorem to perform your desired computation modulo the factors, then it will usually be cheaper to do it that way.

  • 2
    $\begingroup$ That seems like a reasonable rule of thumb, but I'll point out that $(\log a + \log b + \log c)^2 \leq 3 ((\log a)^2 + (\log b)^2 + (\log c)^2)$, so it won't make a big difference. $\endgroup$ Dec 8, 2022 at 14:02
  • $\begingroup$ @DavidESpeyer It does when $3 \to \infty$, doesn't it? $\endgroup$
    – Aurel
    Dec 8, 2022 at 16:42
  • $\begingroup$ @Aurel Once 3 goes to infinity you can't dismiss the subsequent multiplications of the mod a/b/c inverses over mod n as Timothy Chow has, and then you see the complexity is still only a constant away. Not to mention there's a quasi linear version of Euclid's algorithm which is better applied as 3 goes to infinity and used in the OP's idea $\endgroup$ Dec 8, 2022 at 21:21
  • $\begingroup$ I suppose if we were in a position to choose the mods ahead of time and just hardcode the inverses, we get to skip all those steps at run-time. But even just comparing addition and multiplication steps, I think it's 2n vs 3n calculations. Fairly insignificant savings at the best of times. Thanks for the help! $\endgroup$
    – coolpapa
    Dec 9, 2022 at 17:28

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.