1
$\begingroup$

$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.

$\endgroup$
  • 1
    $\begingroup$ Wikipedia: Chinese remainder theorem $\endgroup$ – Martin Sleziak Oct 18 '15 at 11:32
  • 1
    $\begingroup$ One possible approach: The first congruence says that $x=2k$ for some integer $k$. So you know that $2k\equiv0\pmod3$. What can you say about $k$ from this? (You should get that $k=3l$ and $x=6l$. Plug this into the next congruence $6l\equiv1\pmod5$ and continue like this. $\endgroup$ – Martin Sleziak Oct 18 '15 at 11:35
1
$\begingroup$

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}

$\endgroup$
0
$\begingroup$

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 .

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

enter image description here

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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