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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there any way to solve for $x$ in a system of linear congruences with rational coefficients in the following form?

$$Ax \equiv b\pmod 2, \space where\space A \in \Bbb Q^{n,m}, b \in \Bbb Q^m$$

Put another way,

$$ a_{1,1}x_1+a_{2,1}x_2+\dots+a_{n,1}x_n \equiv b_1 \pmod 2 \\ a_{1,2}x_1+a_{2,2}x_2+\dots+a_{n,2}x_n \equiv b_2 \pmod 2 \\ \vdots \\ a_{1,m}x_1+a_{2,m}x_2+...+a_{n,m}x_n \equiv b_m \pmod 2 $$

with $a_{i,j}, b_j \in \Bbb Q$

share|cite|improve this question
Yes, multiply both sides of each congruence by the least common divisor of all the denominators of the rational coeiffients, this should turn it into a system of congruences with integer coeiffients, now obtain a least common divisor for each coeiffient corresponding to each $x_j$, and scale them appropietly, such that when you subtract corresponding congruences this term will be eliminated, (its essentially gauss jordon elimination except, we can only scale by integers, because were working with congruences), just do this until you can isolate a congruence with a single $x_j$, and solve 4 it. – Ethan Jan 23 '13 at 0:23
@Ethan Thanks! Wow, that almost seems too easy. So multiplying both sides is a valid operation under congruence? This note from Wikipedia made me think not: "The next property, however, would fail if these variables were not all integers", which then demonstrates multiplication. – Joe Jan 23 '13 at 3:45
You can not multiply both sides of a congruence by a rational number is what there referring to, but you can by an integer. – Ethan Jan 23 '13 at 4:11

Your Answer


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

Browse other questions tagged or ask your own question.