I’m given
-
a_1, a_2,\dots,a_n,
-
b_1,b_2,\dots,b_n,
- an upper bound U,
- and n linear equations of the form:
k_1 * a_1 + b_1 = x
k_2 * a_2 + b_2 = x
\dots
k_n * a_n + b_n = x
Additional info where r \in \{ 1,2,\dots , n \}:
-
a_r is prime
- 0 \leq b_r < a_r
-
k_r b_r, U, n, \in N_0 and (a_r\in N)
-
k_r has to be determined such that x can be determined
I’m looking for an algorithm that computes the largest x which satisfies all of the given equations such that for the given upper bound U the additional constraint x \leq U holds. If there is no such x a simple “no solution” as output is fine.
First Example:
Given data:
a_1 = 3, a_2 = 5 and b_1 = 1, b_2 = 2 and U = 20
The n equations with substituted values:
k_1 * 3 + 1 = x
k_2 * 5 + 2 = x
The solution (largest x which satisfies the equations and is \leq U is 7 (set k_1 = 2 and k_2=1)
Second Example:
Given data:
a_1 = 11, a_2 = 17 and b_1 = 1, b_2 = 2 and U = 20
The n equations with substituted values:
k_1 * 11 + 1 = x
k_2 * 17 + 2 = x
The solution (largest x which satisfies the equations and is \leq U is “no soluton” (there is no way to set k_1 and k_2 such that the equations are equal)
I’m struggling to come up with an algorithm which solves this efficiently. Currently my best approach is to compute all values of x which satisfy the first equation (by iterating through all possible values of k_1 such that x \leq U, then I compute all values of x which satisfy the second equation and so on until I have n sets, set i represents the values of x which satisfy equation i. Then I simply intersect all of them, if the result is an empty set then I output “no solution” otherwise I output the max element of the resulting set. This approach is very inefficient 
What do you think about my approach how could I compute the largest x which satisfies all of the constraints above more efficiently?
Note: I’m expecting that the solution will use elementary number theory since prime numbers are involved. I just don’t know how else to approach this.
1 Like
The given n linear equations can be restated as
x \equiv b_1 \pmod{a_1} \\
x \equiv b_2 \pmod{a_2} \\
... \\
... \\
x \equiv b_n \pmod{a_n}
Enter the Chinese Remainder Theorem, which states that given such a system of n equations where a_1, a_2, ... , a_n are pairwise coprime, there exists a unique solution for x modulo A where A = a_1 a_2... a_n, and this solution can be determined efficiently. Since each a_r is prime for 1 \le r \le n in this problem, a_1, a_2, ... , a_n are surely pairwise coprime and the theorem can be applied.
Here is a short and simple description of the theorem: link. You should be able to find various other resources on the theorem and its implementation on the internet if necessary. You should also get familiar with modular arithmetic if you aren’t already.
After using the theorem to determine the unique solution y such that x \equiv y \pmod A, it is a trivial matter to calculate the largest x \le U.
Hope this helps 
3 Likes
How would you determine that the output should be “no solution” like in the second example?
Is there an alternative solution in the case where a1,a2,…,an are prime but not coprime?
After we find y such that x \equiv y \pmod{A}, it means that all suitable x are of the form kA+y where k is any integer. If we are dealing with positive values only (0 \le x \le U), which your question seems to imply, then 0 \le k. Consequently, there will be no solution when the smallest suitable x (for k=0) is greater than U. Hence there is no solution when y > U.
If you have instances where x \equiv b_i \pmod{a_i} and x \equiv b_j \pmod{a_j} where a_i=a_j, b_i \ne b_j, obviously no solution exists to the system of equations since x cannot possibly give two distinct remainders (b_i and b_j) on being divided by the same number (a_i).
@meooow
The answers over here: https://math.stackexchange.com/questions/120070/chinese-remainder-theorem-with-non-pairwise-coprime-moduli are confusing me.
What you say makes sense, if a_i = a_j then b_i = b_j must hold, otherwise there is no solution. In the case that a_i = a_j and b_i = b_j I can compute the result by simply ignoring the equations with duplicate moduli (counting them only once) right?
The math.stackexchange post deals with a more general case of non pairwise coprime moduli, which are not limited to primes as in this problem.
And yes, if you are given duplicate (a_i, b_i) values you can simply take one of them into consideration and ignore the rest.