Tell me more ×
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.
up vote 0 down vote favorite

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|improve this question
1  
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 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 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 at 4:11

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.