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.