Exercise 2.3.2 (First examples, part 2)

Question

Find all integers that satisfy simultaneously: $x\equiv 2 \pmod 3, x \equiv 3 \pmod 5, x \equiv 5 \pmod 2$.

Richard Ganaye · Accepted Answer

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

\begin{proof} Write $(a_1,a_2,a_3) = (2,3,5)$, $(m_1,m_2,m_3) = (3,5,2)$, and $m = m_1 m_2 m_3 = 30$.
Here $m_1,m_2,m_3$ are relatively prime by pairs.

Consider, as in the proof of the Chines remainder theorem
$$(m'_1,m'_2,m'_3) = (m/m_1, m/m_2,m/m_3) = (10, 6, 15).$$
Since $ m'_1 = 10 \equiv 1 \pmod 3, m'_2 = 6 \equiv 1 \pmod 5, m'_3=15 \equiv 1 \pmod 2$, the inverses $b_i$ of $m'_i$ modulo $m_i$ are 
$$(b_1,b_2,b_3) = (1,1,1),$$
Therefore a particular solution is given by
$$x_0 = m'_1 b_1 a_1 + m'_2b_2 a_2 + m'_3b_3a_3 = 10\cdot 2 + 6 \cdot 3 + 15 \cdot 5 = 113 .$$
A smaller one is $x_1 = 113 - 3\cdot 30 = 23$.

(check: $23 \equiv 2 \pmod 3, 23 \equiv 3 \pmod 5, 23 \equiv 5 \pmod 2$.)

Then
\begin{align*}
&x\equiv 2 \ \pmod 3, x \equiv 3 \  \pmod 5, x \equiv 5 \pmod 2\
 \iff &x\equiv 23 \pmod 3, x \equiv 23 \pmod 5, x \equiv 23 \pmod 2\
\iff & 3 \mid x - 23, 5 \mid x- 23, 2 \mid x-23\
\iff &30 \mid x-23\
\iff &\exists k \in \Z,\ x= 23 + 30k.
\end{align*}

The integers that satisfy simultaneously: $x\equiv 2 \pmod 3, x \equiv 3 \pmod 5, x \equiv 5 \pmod 2$ are the integers $23 + 30k$, where $k$ is any integer.
\end{proof}

Exercise 2.3.2 (First examples, part 2)

Answers

Comments

Exercise 2.3.2 (First examples, part 2)

Answers

Comments

Add answer