0
$\begingroup$

I need to know if some system of congruences of form:

$$x \equiv a_1 \pmod{b_1}$$ $$\ldots$$ $$x \equiv a_n \pmod{b_n}$$ has a solution and how big this solution could be. I can't assume that b are relatively prime so I can't use Chinese remainder theorem. Any ideas?

$\endgroup$
  • $\begingroup$ Do you know how to deal with the case $n = 2$? If so, you can, if nobody has a better idea, iterate until you either reach the end and have a solution, or find out that no solution exists. $\endgroup$ – Daniel Fischer Nov 11 '16 at 16:57
  • $\begingroup$ I don't even need to find the solution. I only want to know if such solution exists and how big it is. $\endgroup$ – John Cyna Nov 11 '16 at 16:59
1
$\begingroup$

A solution exists $\iff \gcd(b_i,b_j)\mid a_i-a_j\,$ for all $\,i\ne j,\,$ i.e. iff they are pairwise solvable. See this answer for a proof.

Any solution is unique mod $m = $ lcm of all moduli, so the least natural solution can be as large as $\,m-1,\,$ e.g. $\, x\equiv -1 \pmod {b_i}\iff x\equiv -1\pmod m\,$ has least solution $\, x = m-1$

Indeed if $\,x'$ and $\,x\,$ are solutions then all $\ b_i\mid x'-x\,$ so $\ m = {\rm lcm}\{b_i\}\mid x'=x,\ $ i.e. $\,x'\equiv x\pmod m.\,$ Conversely $\,x'\equiv x\pmod{m}\,\Rightarrow\,x'\equiv x[\equiv a_i]\pmod{b_i}\,$ by $\,b_i\mid m.$

$\endgroup$
0
$\begingroup$

Try to find partial solutions $x_1, ..., x_n$ such that $x_i \equiv \delta_{i,j} \pmod{b_j}$ for all $i,j \in [1,n]$ (where $\delta$ is the Kronecker delta function).

You can do so by trying integers in $\text{lcm}_{j\ne i}(a_j)\Bbb Z$

You'll find that $x = \sum_{i=1}^n a_i x_i$ is solution to your system.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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