Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding smallest solution to modular equations

  1. Feb 22, 2013 #1

    I have gotten the task of finding the smallest number which is:
    1 or 2 mod 3
    0 mod 4
    0 or 1 or 4 mod 5
    1, 2, 5, 6, 9 or 10 mod 11

    I have also been given that the smallest number is in the range [10,50].

    Now, it is quite easy to see that 16 is the smallest number creating a solution.
    But my question is if there are any known algorithm for finding the smallest possible solution besides lining up all 2*1*3*6 modular equations and solving them?

  2. jcsd
  3. Feb 23, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper

    Welcome to PF!

    Hallo Das Bot! Welcome to PF! :smile:
    Not that I know of. :redface:

    But you can shorten it a lot by starting with 0 mod 4: that means it must be 12, 16, 20 …

    and all you need do is check 12 (nooo), 16 (yesss!), and you're there! :wink:
  4. Feb 23, 2013 #3
    I would add that, given that the moduli 3,4,5,11 are pairwide coprime, you are guaranteed that a solution exists, and tiny-tim's algorithm (were you to choose any other numbers in the LHS of the congruencies) would always terminate. Without going farther than 3*4*5*11 - 4 = 656, worst case.
  5. Feb 23, 2013 #4
    Thank you for the replies :)

    Simply adding 4 will surely give an answer, but when at some point I am dealing with houndreds of congruences and an answer in the range [10^20, 10^25] this is proving too slow.

    My present algorithm for finding a solution is to line up the equations, and if some point the range-restrictions cannot be fulfilled, I stop checking that "solution-chain".

    For example: I choose to believe that the solution is:
    1 mod 3
    0 mod 4
    4 mod 5
    And 4 mod 60 does give a solution to the three congruences.
    But by now I can see, that 60 > 50 and 4 < 10, and therefore there is no need to check the systems mod 11 (and possibly more systems), since the lowest possible solution is 4 and the second lowest has to be at least larger than 60.

    I don't even know if the problem of finding lowest solution is in P, but I would suspect it to be in NP if I did not have the range-restrictions.
    If so, how can I prove that the problem is in NP?
    Last edited: Feb 23, 2013
  6. Feb 23, 2013 #5
  7. Feb 24, 2013 #6
  8. Feb 24, 2013 #7
    I was thinking on similar lines. If N is the number of congruences, and if the number of left-hand-side possibilities for the congruences is bounded (say, no more than K, where K does not depend on how big your numbers are), then you may have to use the Chinese Remainder Theorem a maximum of K^N times (worst case), and then choose the smallest of these results. I think that would make the problem NP if K>1. But, in practice, if that number does not really approach K^N, then repeating the CRT could be a viable algorithm.

    In your example, there are 4 congruences (N=4), and there are no more than 6 values (K=6) on the left-hand side. However, the number of times you have to apply the CRT is 2*1*3*6, much smaller than 6^4, and that number does not depend on whether your solution is in [10,50] or in [10^20, 10^25].
  9. Feb 24, 2013 #8
    Well, aside from 4, the each congruence will have at most (p+1)/2 values for a prime p.
    So the number of possibilities will roughly be the product of the first N primes (aside from 2, for which 4 is used instead) divided by 2^N.

    For many congruences, this gives way too many possibilities to test, which is why I was hoping for someone to know of an algorithm :smile:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook