I have $a_1, a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$ and 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)$
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, 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: the reason I know that there is a more efficient solution is because I have encountered this problem during a programming competition. 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.