0
$\begingroup$

Let $p$ be a prime. Consider the following congruences:

$$ \begin{array}{lcl} a_1 x & = & c_1 (\text{mod } p) \\\\ \vdots & & \vdots\\\\ a_n x & = & c_n (\text{mod } p) \\ \end{array} $$

Obviously, there is a solution $x$ to this system if and only if $c_1 / a_1 \equiv \ldots \equiv c_n/a_n$. I'd like to know if there is such a, sufficient and necessary, condition for more complex congruences like:

$$ \begin{array}{lcl} a_1 x + b_1 y& \equiv & c_1 (\text{mod } p) \\\\ \vdots & & \vdots\\\\ a_n x + b_n y& \equiv & c_n (\text{mod } p) \\ \end{array} $$

I'm actually interested in the case where there are $m$ variables, but the case of $m=2$ is also of interest to me. I know I could use linear algebra to solve Ax = c, but I'd like some conditions which can be tested locally.

Improve this question
$\endgroup$
5
  • $\begingroup$ Carl - this question will probably get closed soon since it is more appropriate for math.stackexchange.com. However, two comments: (1) What are the conditions for such a system of equations to be soluble over the real numbers? If you can't answer this, you should read up on linear algebra first. (2) The integers modulo p form a field, so pretty much everything you know about linear algebra over the reals works mod p without any changes. $\endgroup$
    – Martin Bright
    Commented Sep 28, 2011 at 12:50
  • $\begingroup$ That's not what I'm looking for. I'm looking for local conditions as in the case of proofwiki.org/wiki/Solution_to_Simultaneous_Linear_Congruences $\endgroup$
    – Carl
    Commented Sep 28, 2011 at 13:27
  • $\begingroup$ You only have one prime -- you can't get much more local than that. $\endgroup$
    – Igor Rivin
    Commented Sep 28, 2011 at 13:40
  • $\begingroup$ For example, is it true that there exists a solution to each pair of congruences if there exists one to the whole system? $\endgroup$
    – Carl
    Commented Sep 28, 2011 at 13:44
  • 4
    $\begingroup$ @Carl: Watch your logical connectives! The question you just asked is totally vacuous. I think you meant "... only if there exists one to the whole system". Here the answer is (almost as obviously) no: consider the equations $x+y=1, x=0, y=0$ -- any two of these are simultaneously solvable but the three are obviously not simultaneously solvable. But to reiterate what others have already said, with coefficients in $\mathbb{R}$ these would be totally trivial undergraduate linear algebra exercises, and linear algebra over $\mathbb{F}_p$ works just the same. $\endgroup$
    – David Loeffler
    Commented Sep 28, 2011 at 15:59

1 Answer 1

Reset to default
2
$\begingroup$

See http://en.wikipedia.org/wiki/Gaussian_elimination

Everything it says works for $\mathbb{F}_p,$ since that is (luckily) a field.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .