Find solutions of linear congruences: $x\equiv 0 \pmod 2$ , $x\equiv 0 \pmod 3$, $x\equiv 1 \pmod5$, $x\equiv 6 \pmod7$

Question

$x\equiv 0 \pmod 2$
$x\equiv 0 \pmod 3$
$x\equiv 1 \pmod5$
$x\equiv 6 \pmod7$
Find all the solutions of each of the following systems of linear congruences.

I know how to find solutions of three congruence equations, but I don't know how to solve the 4 equations system... I can't find it in my text book but it is in exercise sample... help me pls.

Answer 1

Hint: You can easily guess one solution. (What is the smallest positive integer which is both even and multiple of 3)?

If you know Chinese remainder theorem then you know that once you have one solution $x_0$ all other solutions will be $$x\equiv x_0 \pmod{210}.$$

Of course, this can be solved also without guessing. (And for larger numbers it would be difficult to guess one solution.)

For a more systematic approach you can see the Wikipedia article I linked above, you can try the hint I have given in a comment or you can look on some other posts on this site tagged congruences+systems-of-equations or chinese-remainder-theorem.

Answer 2

Notice that $6$ is a solution of the given system of linear congruences. By the Chinese remainder theorem, any other integer solution is of the form $$6+2\cdot3\cdot5\cdot7\cdot k=6+210\cdot k$$ with $k\in\mathbb{Z}$, Conversely, one easily sees that any such number is a solution of the congruences.

Answer 3

The big idea is that the mapping $$f:\mathbb Z_{210} \to \mathbb Z_2 \times \mathbb Z_3 \times\mathbb Z_5 \times\mathbb Z_7$$ (where $210 = 2\cdot3\cdot5\cdot7$) defined by $f(\bar n)= (\bar n,\bar n,\bar n,\bar n)$ is an isomorphism between additive groups.

You need to find an integer, $n$, such that $f(\bar n) = (\bar 0, \bar 0, \bar 1, \bar 6)$.

Because $f$ is an isomorphism, there exists $e_1, e_2, e_3, e_4 \in \mathbb Z_{210}$ such that \begin{align} f(e_1) &= (\bar 1, \bar 0, \bar 0, \bar 0)\\ f(e_2) &= (\bar 0, \bar 1, \bar 0, \bar 0)\\ f(e_3) &= (\bar 0, \bar 0, \bar 1, \bar 0)\\ f(e_4) &= (\bar 0, \bar 0, \bar 0, \bar 1) \end{align}

It follows that $$n \equiv 0 e_1 + 0 e_2 + 1 e_3 + 6 e_4 \equiv 1 e_3 + 6 e_4 \pmod{210}.$$

We compute $e_3$

Because $e_3 \equiv 0$ modulo $2$, modulo $3$, and modulo $7$, then $e_3$ is a multiple of $42 = 2\cdot3\cdot 7$.
So $e_3 \equiv 42x \pmod{210}$ for some integer, $x$.
Because $e_3 \equiv 1 \pmod 5,$ \begin{align} 42x &\equiv 1 \pmod 5 \\ 2x &\equiv 1 \pmod 5 \\ x &\equiv 3 \pmod 5 \end{align}
So $e_3 \equiv 42\cdot3 \equiv 126 \pmod{210}$

We compute $e_4$

Because $e_4 \equiv 0$ modulo $2$, modulo $3$, and modulo $5$, then $e_4$ is a multiple of $30 = 2\cdot3\cdot 5$.
So $e_4 \equiv 30x \pmod{210}$ for some integer, $x$.
Because $e_4 \equiv 1 \pmod 7,$ \begin{align} 30x &\equiv 1 \pmod 7 \\ 2x &\equiv 1 \pmod 7 \\ x &\equiv 4 \pmod 7 \end{align} So $e_4 \equiv 30\cdot4 \equiv 120 \pmod{210}$

We compute $n$

\begin{align} n &\equiv 1 e_3 + 6 e_4 \pmod{210}\\ &\equiv 1 \cdot 126 + 6 \cdot 120 \pmod{210}\\ &\equiv 126 + 90 \pmod{210} \\ &\equiv 6 \pmod{210} \end{align}

Answer 4

A linear system of congruencies is equivalent to a linear system of equations where the coefficients and variables are elements of the set of Integers (Z). It is possible to solve a linear system of equations in Z by symbolic manipulation using the “generally accepted definitions, laws and theorems” for the set of Integers. The method of substitution is used in two ways in the manipulations. For the first way, substitution is used to add parameter variables and corresponding equations. For the second way, substitution is used to eliminate variables from existing equations. By judiciously applying the method of substitution in these two ways, a basis can be found where every original variable is expressed in terms of parameter variables.

A guiding principle in applying the method of substitution is to express the original variables in terms of parameter variables.

Based on the symbolic manipulations, it is possible to work with an augmented matrix instead of directly manipulating the symbols; in other words, perform matrix operations on the augmented matrix. This reduces the amount work and the time needed to find a basis. The following presents a solution to the problem using symbolic manipulations. Highlights of the manipulations are presented as augmented matrices.

An answer to the problem: x=6+210t_4 or x≡6 (mod 210).

Reference

Chionglo, J. F. (2015). A Reply to "Find Solutions to Linear [Congruencies]". Available at http://www.aespen.ca/AEnswers/1447217299.pdf.

“Find Solutions of Linear Congruences” (2015). Mathematics Stack Exchange. Retrieved on Nov. 10, 2015 from Find solutions of linear congruences: $x\equiv 0 \pmod 2$ , $x\equiv 0 \pmod 3$, $x\equiv 1 \pmod5$, $x\equiv 6 \pmod7$.