# 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'm sure there are better ways if some more information is present, but I don't really know much about solutions of such systems. You might want to have a look at the Chinese Remainder Theorem, as it is concerned with a similar situation. – Ittay Weiss Mar 8 '13 at 9:42
• I already looked into the CRT but cannot manage to map it to the above problem, as it has two unknowns per equation. Thanks again! – ws6079 Mar 8 '13 at 9:45
• then you can ignore my suggestion ;). In any case, you're welcome and good luck! – Ittay Weiss Mar 8 '13 at 9:48

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.

x+y ≡ d (mod p)

d ≡ (x (mod p)) + (y (mod p)) (mod p)

Example:

a ≡ 1 mod 3, b ≡ 2 mod 3, a + b ≡ 3 mod 3 ≡ 0,

Also:

xa ≡ d (mod p), d = c (mod p),

c = a (mod p) iff (a (mod p) > x (mod p) or a (mod p) = x (mod p) OR a (mod p) is = 0) c = x (mod p) iff (x (mod p) > a (mod p) or x (mod p) = a (mod p) OR a (mod p) is = 0)