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

$\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,

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,

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:

where $\displaystyle c_i = \frac{b_i}{d_i}t_i$ and $\displaystyle m_i = \frac{n_i}{d_i}$.

$\Box$

# posted by rot13(Unafba Pune) @ 9:14 AM