Finding smallest solution to modular equations

  • Thread starter Das Bot
  • Start date
In summary, the conversation discusses the task of finding the smallest number that satisfies multiple modular equations, with a given range restriction. The idea of using the Chinese Remainder Theorem is mentioned as a possible algorithm, but its efficiency is questioned. The conversation ends with a hope for a more efficient algorithm.
  • #1
Das Bot
4
0
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
 
Physics news on Phys.org
  • #2
Welcome to PF!

Hallo Das Bot! Welcome to PF! :smile:
Das Bot said:
… 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. :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:
 
  • #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.
 
  • #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:
  • #6
  • #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].
 
  • #8
Dodo said:
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 :smile:
 

1. What is a modular equation?

A modular equation is an equation that involves modular arithmetic, where the unknown variable is taken modulo a certain number. In other words, the solution to a modular equation is the smallest positive integer that satisfies the equation when it is divided by the specified number.

2. Why is finding the smallest solution important?

Finding the smallest solution to a modular equation is important because it allows us to simplify and reduce the complexity of mathematical problems. It also helps in finding patterns and making predictions in number sequences.

3. How do you find the smallest solution to a modular equation?

To find the smallest solution to a modular equation, we use the process of trial and error. We start by plugging in small positive integers for the unknown variable until we find one that satisfies the equation when it is divided by the specified number.

4. What is the role of the modulus in a modular equation?

The modulus in a modular equation determines the range of possible solutions. It is the number by which the unknown variable is divided, and it helps us to find the smallest solution within a specific range.

5. Can a modular equation have more than one solution?

Yes, a modular equation can have multiple solutions. However, we are interested in finding the smallest solution, which is the only unique solution to the equation when it is divided by the specified number.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
705
Replies
11
Views
367
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
300
  • General Math
Replies
5
Views
982
  • Precalculus Mathematics Homework Help
Replies
3
Views
846
  • Linear and Abstract Algebra
Replies
1
Views
862
  • Quantum Physics
Replies
3
Views
907
  • Linear and Abstract Algebra
Replies
1
Views
717
Replies
5
Views
2K
Back
Top