Algorithm which finds the maxmal solution that satisfies the following constraints 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 &lt; 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.
You want a solution $x$ such that

$$x \equiv b_i \pmod{a_i}$$

for all $i$.  By the Chinese remainder theorem, this is either impossible or it is equivalent to

$$x \equiv b \pmod{a}$$

where $a = \text{lcm}(a_1,\dots,a_n)$ and $b$ can be computed using the Chinese remainder theorem.  In other words, the solutions are all of the form $b$, $b+a$, $b+2a$, $b+3a$, etc.  From there it is easy to find the largest solution $x$ such that $x\le U$.