0
$\begingroup$

I need to resolve the following system of linear congruences:

$9 = 3a+c \pmod m$
$11 = 9a+c \pmod m$
$1 = 11a+c \pmod m$

How can I proceed?
Is there anyway to input these equations in Wolfram alpha (or another tool)?

$\endgroup$
1
  • 1
    $\begingroup$ Certainly one can proceed to try and solve these congruence modulo $m$ without knowing much about $m$. You might want to specify what values $m$ is allowed to take, though. $\endgroup$
    – hardmath
    Jul 16 '16 at 21:18
1
$\begingroup$

We note that (for a fixed $m$) we have three linear congruences in two variables, so there is no particular reason to suppose that a solution exists. Indeed, for most $m$, no solution exists...as what follows will show.

Subtracting the first from the second we get $$6a\equiv 2 \pmod m$$

Subtracting the second from the third gives $$2a\equiv -10 \pmod m$$

Combining these give $$6a\equiv 3\times 2a\equiv 3\times (-10)\equiv -30\equiv 2\pmod m$$

Thus, $m$ divides $32$, so $m=2^n$ for $n≤5$

We will consider the case $m=32$.

The congruence $6a\equiv 2 \pmod {32}$ has solutions $a=11,27$. These give rise to the solutions $$(a,c)\equiv (11,8)\;or\;(27,24)\pmod {32}$$

The other cases for $m$ are similar.

$\endgroup$
9
  • 1
    $\begingroup$ In fact one can easily generate all solutions mod $\,2^i < 32\,$ by modular reduction and adding in the obvious homogeneous solution $\,(a,c) = (m/2,m/2),\,$ see my answer. $\endgroup$ Jul 17 '16 at 1:02
  • 1
    $\begingroup$ Very clean, thanks! $\endgroup$
    – lulu
    Jul 17 '16 at 1:09
  • $\begingroup$ I see but you had to pose a value fo m. Can't it be deducted? $\endgroup$
    – Rafa
    Jul 17 '16 at 3:18
  • 1
    $\begingroup$ @Rafa Perhaps I should have stressed that the method I proposed to finish might require more effort if you are not already familiar with the relationship between nonhomogeneous and homogeneous solutions of linear equations (though it is very easy to learn even if you never studied linear algebra). But once you know that it will save you work, esp. if you have analogous larger systems with higher powers. $\endgroup$ Jul 17 '16 at 21:16
  • 1
    $\begingroup$ @Rafa Moreover, this fundamental result on solutions of linear equations is ubiquitous so the sooner you learn it the better. You will need if for solutions of differential and difference equations (recurrences). linear Diophantine equations, etc. $\endgroup$ Jul 17 '16 at 21:16
1
$\begingroup$

Given the solutions mod $2^5$ in lulu's answer, I explain how to very simply generate the solutions mod $\,2^i\,$ for all $\,i\le 4.\,$ Doing the same elimination lulu did for the homogeneous system with $9,11,1$ replaced by $\,0,0,0$ we get $\,0 \equiv 2a\equiv 6a \equiv 8a \!\iff\! 2a \equiv 0.\,$ So $\,a \equiv 0\pmod {\!m/2}$ and this implies $\,c\equiv 0\pmod{\!m/2}.\,$ Hence two solutions differ by multiple of $\,(m/2,m/2).\,$ So given any particular solution $\,(a,c),\,$ there will be one other solution $(a,c)+(m/2,m/2).\,$ But we already know a particular solution: $ $ reduce mod $\,m = 2^i$ the solution mod $\, 2^{i+1}.$

For example, the solutions $\,(a,c)\equiv (11,8),(27,24)\pmod{\!2^5}\,$ reduce to the solution $\,(11,8)\pmod{\!2^4}.$ The other solution(s) arise by adding multiples of $\,(m/2,m/2)=(8,8),\,$ hence there is one other solution $\,(11,8)+(8,8)\equiv (3,0)$.

These map to $\,(3,0)\pmod{\!2^3}\,$ with one other solution $\,(3,0)+(4,4)\equiv (7,4),\,$

These map to $\ \ \: \ldots\pmod{\!2^2}\, $ with $\ \ldots$

$\endgroup$

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