Exercise 2.3.21* (Solve $x\equiv a_i \pmod{p^{\alpha_i}},\ i=1,\ldots,r$)

Question

Let $p$ be a prime number, and suppose that $m_j = p^{\alpha_j}$ in (2.1), i.e.
$$x\equiv a_1 \pmod{m_1},\qquad x\equiv a_2 \pmod{m_2},\ \cdots,\qquad  x\equiv a_r \pmod{m_r} \qquad (2.1)$$
where $1\leq \alpha_1\leq \alpha_2\leq \cdots \leq \alpha_r$. Show that the system has a simultaneous solution if and only if $a_i \equiv a_r \pmod {p^{\alpha_i}}$ for $i = 1,2,\ldots,r$ (*).

\bigskip
(*)Misprint in the original sentence, which gives the condition $a_i \equiv a_r \pmod {p^{\alpha_r}}$ (see discussion below).

Richard Ganaye · Accepted Answer

Note that the system
$$x \equiv 1 \pmod 2,\qquad x \equiv 3 \pmod 4,\qquad x \equiv 7 \pmod 8$$
 has the solution $7$, but $3 
ot \equiv 7 \pmod 8$. So the original condition $a_i \equiv a_r \pmod {p^{\alpha_r}}$ is false, and must be replaced by $a_i \equiv a_r \pmod {p^{\alpha_i}}$

\begin{proof} Let $S$ be the system
$$x\equiv a_1 \pmod{p^{\alpha_1}},\qquad x\equiv a_2 \pmod{p^{\alpha_2}},\ \cdots,\qquad  x\equiv a_r \pmod{p^{\alpha_r}}\qquad (2.1)$$
\begin{enumerate}
\item[$(\Rightarrow)$] Suppose that $S$ has a solution $x \in \Z$. Since $1\leq \alpha_1\leq \alpha_2\leq \cdots \leq \alpha_r$, 
$$p^{\alpha_i} \mid p^{\alpha_r}, \qquad i=1,\ldots,r.$$
Therefore, for every $i \in [\![1,r]\!]$, $ x\equiv a_r \pmod{p^{\alpha_r}}$  implies  $x\equiv a_r \pmod{p^{\alpha_i}}$. Moreover $ x\equiv a_i \pmod{p^{\alpha_i}}$, thus $a_i \equiv a_r \pmod {p^{\alpha_i}}$.
\item[$(\Leftarrow)$] Suppose that $a_i \equiv a_r \pmod {p^{\alpha_i}}$ for $i =1,\ldots,r$. Take $x =a_r$. Then
$$x =a_r \equiv a_i \pmod{p^{\alpha_i}}.$$
\end{enumerate}
The system has a simultaneous solution if and only if $a_i \equiv a_r \pmod {p^{\alpha_i}}$ for $i = 1,2,\ldots,r$
\end{proof}

Exercise 2.3.21* (Solve $x\equiv a_i \pmod{p^{\alpha_i}},\ i=1,\ldots,r$)

Answers

Comments

Exercise 2.3.21* (Solve $x\equiv a_i \pmod{p^{\alpha_i}},\ i=1,\ldots,r$)

Answers

Comments

Add answer