Exercise 2.3.6 (First examples, part 6)

Question

Solve Example 1 by the method used in the second solution of Example 3.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

\begin{proof} The system given in Example 1 is
\begin{align}
x \equiv 5 \pmod 7, \qquad x \equiv 7 \pmod {11}, \qquad x \equiv 3 \pmod {13}.
\end{align}
The last equation gives $x = 3 + 13u,\ u \in \Z$. On substituting this into the second congruence, we obtain
\begin{align*}
3 + 13 u &\equiv 7 \pmod{1},\
13 u & \equiv 4 \pmod{11},\qquad (6 	imes 13 \equiv 1 \pmod 11)\
u &\equiv 6 	imes 4  \equiv 2 \pmod {11}.
\end{align*}
So $u = 2 + 11v$ for some integer $v$, therefore
$$x = 3 + 13(2 + 11v) = 29 + 143 v\qquad(v \in \Z).$$
using the first congruence,
\begin{align*}
29 + 143 v &\equiv 5 \pmod 7,\
143 v &\equiv 4 \pmod 7,\
3v &\equiv 4 \pmod 7,\
v &\equiv -1 \pmod 7.
\end{align*}
So $v = -1 + 7w$ ofr some integer $w$, thus
$$x = 29 + 143(-1 + 7v) = -114 +1001 v.$$
The solutions are $x \equiv -114 \equiv 887 \pmod {1001}$ (and conversely, every $x \equiv 887 \pmod {1001}$ is a solution).

The system (1) is equivalent to
$$x \equiv 887 \pmod{1001}.$$
\end{proof}

Exercise 2.3.6 (First examples, part 6)

Answers

Comments

Exercise 2.3.6 (First examples, part 6)

Answers

Comments

Add answer