I am self studying analytic number theory from Tom Apostol and couldn't solve this particular question which is 8(a) of chapter 8 on page 175.
It's image:
Attempt: I thought of proving that for every $a_i$ that satisfies $a\equiv a_{i} (mod k_i) $ will satisfy $a_{i} \equiv 1 (mod k_j) $ .
But I couldn't. Also, I realized that this will not prove existence of $a_i$ .
So, I am struck on this problem and need your help.
Thanks
Best Answer
Let $n$ be the product of all $k_j$ for $j \neq i$. Then since the positive integers $k_i$ are all relatively prime in pairs, this means $\gcd(k_i, n) = 1$. The Chinese remainder theorem states there's a solution for $a_i$ in the system of
$$a_i \equiv a \pmod{k_i} \tag{1}\label{eq1A}$$
$$a_i \equiv 1 \pmod{n} \tag{2}\label{eq2A}$$
From \eqref{eq2A}, the modulo equation also holds for all factors of $n$, i.e., we then have
$$a_i \equiv 1 \pmod{k_j} \; \forall \; j \neq i \tag{3}\label{eq3A}$$
Note you could also have just used the set of all $n_j$ congruences instead with the Chinese remainder theorem as the only condition is the moduli are all pairwise coprime.