# System of equations modulo primes

Is it generally possible to solve a set of linear equations modulo some prime numbers $\{p,q,r\}$. For example if I have the following congruences:

$$xa_p + yb_p \equiv d \pmod {p}\\ xa_q + yb_q \equiv d \pmod {q}\\ xa_r + yb_r \equiv d \pmod {r}\\$$

for some known $a_i$ and $b_i$ with $i \in \{p,q,r\}$ can I determine $d$ (assuming a solution exists and $d<p,q,r$)?

Thanks in advance! (and sorry if this is trivial.)

EDIT: Additionally, $a_i$ and $b_i$ are congruences of some unknown (and large) integers $a,b$. (i.e. $a\equiv a_i \pmod{i}$ and $b\equiv b_i \pmod{i}$ )

Any pointers are be welcome! Also knowing that there is no "good" algorithm for this problem would also help me a lot.

-

Since the problem is finite, a brute force approach will either find a solution or prove none exist. In more detail, if $x,y$ is a solution, then $x+kpqr,y+spqr$ is a solution for all $k,s\in \mathbb Z$ (since $pqr=0$ modulo each of $p,q,r$). It thus follows (by using the division algorithm) that if a solution exists then a solution exists with $x,y\in \{0,1,\cdots ,pqr-1\}$. So, the brute force approach will be to iterate over all $0\le x,y< pqr$ and check for solutions. If one is found then you found one, otherwise none exist.
Thank you Ittay! So brute force is the only way to approach this? Would knowing that $a_i$ and $b_i$ are congruences of some unknown (and large) integers $a,b$ help me somehow? (i.e. $a \equiv a_i \pmod{i}$ and $b \equiv b_i \pmod{i}$ –  ws6079 Mar 8 '13 at 9:37
I would take a look at this paper which details a CRT algorithm in multiple variables. However, it is looking at a more specific algorithm - using a known $d$ to solve for $x$ and $y$. It may be a good starting point.