Register to reply 
Finding smallest solution to modular equations 
Share this thread: 
#1
Feb2213, 07:47 PM

P: 4

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 


#2
Feb2313, 04:47 AM

Sci Advisor
HW Helper
Thanks
P: 26,157

Hallo Das Bot! Welcome to PF!
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! 


#3
Feb2313, 05:04 AM

P: 688

I would add that, given that the moduli 3,4,5,11 are pairwide coprime, you are guaranteed that a solution exists, and tinytim'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.



#4
Feb2313, 05:25 AM

P: 4

Finding smallest solution to modular equations
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 rangerestrictions cannot be fulfilled, I stop checking that "solutionchain". 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 rangerestrictions. If so, how can I prove that the problem is in NP? 


#5
Feb2313, 11:52 PM

P: 96

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


#6
Feb2413, 04:44 AM

P: 4




#7
Feb2413, 05:33 AM

P: 688

I was thinking on similar lines. If N is the number of congruences, and if the number of lefthandside 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 lefthand 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]. 


#8
Feb2413, 03:04 PM

P: 4

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 


Register to reply 
Related Discussions  
Finding particular solution to differential equations  Calculus & Beyond Homework  6  
Solving equations and finding solution set  Precalculus Mathematics Homework  2  
Finding a solution to Maxwell's equations from initial datas  Advanced Physics Homework  3  
Differential equations  finding solution  Calculus & Beyond Homework  2  
Differential Equations: Finding the General Solution  Calculus & Beyond Homework  4 