Finding smallest solution to modular equations


by Das Bot
Tags: equations, modular, smallest, solution
Das Bot
Das Bot is offline
#1
Feb22-13, 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
Phys.Org News Partner Science news on Phys.org
Going nuts? Turkey looks to pistachios to heat new eco-city
Space-tested fluid flow concept advances infectious disease diagnoses
SpaceX launches supplies to space station (Update)
tiny-tim
tiny-tim is offline
#2
Feb23-13, 04:47 AM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,167
Hallo Das Bot! Welcome to PF!
Quote Quote by Das Bot View Post
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?
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
dodo is offline
#3
Feb23-13, 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 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
Das Bot is offline
#4
Feb23-13, 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 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
RamaWolf is offline
#5
Feb23-13, 11:52 PM
P: 96
What about the chinese remainder theorem ?
Look at: http://en.wikipedia.org/wiki/Chinese_remainder_theorem
Das Bot
Das Bot is offline
#6
Feb24-13, 04:44 AM
P: 4
Quote Quote by RamaWolf View Post
What about the chinese remainder theorem ?
Look at: http://en.wikipedia.org/wiki/Chinese_remainder_theorem
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
dodo is offline
#7
Feb24-13, 05:33 AM
P: 688
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
Das Bot is offline
#8
Feb24-13, 03:04 PM
P: 4
Quote Quote by Dodo View Post
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].
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


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