Wednesday, January 02, 2013
Ex 2.16 Family of relatively prime
Let \(\{n_i\}_{i=1}^k\) be a pairwise relatively prime family of positive integers. Let \(a_1, \dotsc, a_k\) and \(b_1, \dotsc, b_k\) be integers, and set \(d_i := \gcd(a_i, n_i)\) for \(i = 1,\dotsc,k\). Show that there exists an integer \(z\) such that \(a_iz \equiv b_i \pmod{n_i}\) for \(i=1,\dotsc,k\) if and only if \(d_i \mid b_i\) for \(i=1,\dotsc,k\).
== Attempt ==
\( \implies \)
In general, for every \(b \in \mathbb{Z}\), the congruence \(az \equiv b \pmod n\) has a solution \(z \in \mathbb{Z}\) if and only if \(d \mid b\). Therefore, the only if condition holds.
\( \impliedby \)
Assume \(d_i \mid b_i\), we know there exists a solution \(z_i\) such that \(a_i z_i \equiv b_i \pmod{n_i}\) for \(i=1,\dotsc,k\). In general, for all \(z,z′ \in \mathbb{Z}\), we have \(az \equiv az′ \pmod n\) if and only if \(z \equiv z′ \pmod {\frac{n}{d}} \). Therefore,
| \[ \begin{aligned} a_i \cdot z_i &\equiv b_i \pmod{n_i} \\ \frac{a_i}{d_i}z_i &\equiv \frac{b_i}{d_i} \pmod{\frac{n_i}{d_i}} \\ \end{aligned} \] |
Observe that \( \gcd(\frac{a_i}{d_i}, {\frac{n_i}{d_i}}) = 1 \), which means there always exists a multiplicative modular inverse \(t_i\) such that \( \frac{a_i}{d_i}t_i = 1 \pmod{\frac{n_i}{d_i}} \). So,
| \[ \begin{aligned} \frac{a_i}{d_i} t_i \cdot z_i &\equiv \frac{b_i}{d_i}t_i \pmod{\frac{n_i}{d_i}} \\ z_i &\equiv \frac{b_i}{d_i}t_i \pmod{\frac{n_i}{d_i}} \\ \end{aligned} \] |
Observe that given \(\{n_i\}_{i=1}^k\) are pairwise relatively prime, so are \( \{ \frac{n_i}{d_i} \}_{i=1}^k\). Therefore, by the Chinese remainder theorem, we know there exists a solution \(z \in \mathbb{Z}\) that satisfies this system of congruences:
| \[ \begin{aligned} z &\equiv c_i \pmod{m_i} \mspace20pt (i = 1, \dotsc, k) \end{aligned} \] |
where \(\displaystyle c_i = \frac{b_i}{d_i}t_i\) and \(\displaystyle m_i = \frac{n_i}{d_i}\).\(\Box\)
