Finding smallest solution to modular equations

Das Bot

Hallo

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?

Thanks

tiny-tim

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

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!

dodo

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.

Das Bot

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?

RamaWolf

What about the chinese remainder theorem ?
Look at: http://en.wikipedia.org/wiki/Chinese_remainder_theorem

Das Bot

The chinese remainder theorem will give a solution, but I don't know if the smallest solution will be either 1 or 2 mod 3.

dodo

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].

Das Bot

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