Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.