Suppose $\{n_i\}_{i=1}^k$ are pairwise prime natural numbers, $a_1,\dots,a_k,b_1,\dots,b_k$ are integers, and $d_i = \gcd(a_i,n_i)$ for $i=1,\dots,k$. I want to show that there exists an integer $z$ such that $a_i z \equiv b_i \mod n_i$ for $i=1,\dots,k$ if and only if $d_i \mid b_i$ for $i=1,\dots,k$.

Here is what I have done so far:

"$\Rightarrow$" Suppose there exists an integer $z$ such that $a_i z \equiv b_i \mod n_i$ for $i=1,\dots,k$. Then for some integer $s_i$, $b_i = a_iz + n_is_i$. As $b_i$ can be written as a linear combination of $a_i$ and $n_i$, $b_i \in a_i\mathbb{Z} + n_i\mathbb{Z} = d_i\mathbb{Z}$. As $b \in d_i\mathbb{Z}$, $d_i$ must divide b_i for $i = 1,\dots,k$.

"$\Leftarrow$" Suppose $d_i \mid b_i$ for $i=1,\dots,k$. Since $d_i = \gcd(a_i,n_i)$ and $d_i \mid b_i$ then there exists integers $p_i,q_i$ such that $b_i = a_ip_i + n_iq_i$, and so $b_i \equiv a_ip_i \mod n_i$. As $d_i = \gcd(a_i,n_i)$, $d_i \mid a_i$ and $d_i \mid n_i$; also $d_i \mid b_i$ so $a_i'=a_i/d_i$, $b_i'=b_i/d_i$, and $n_i'=n_i/d_i$ are integers; note that as $\{n_i\}_{i=1}^k$ are pairwise prime natural numbers, $\{n_i'\}_{i=1}^k$ must also be pairwise prime natural numbers. Additionally $a_i'$ and $n_i'$ are relatively prime so there exists $(a_i')^{-1}$ such that $(a_i')^{-1}a_i' \equiv 1 \mod n_i'$, thus $p_i \equiv b_i'(a_i')^{-1} \mod n_i'$. (stuck here)

I do not believe my approach for "$\Leftarrow$" is correct as I have no way to show that each of the $p_i$ are equivalent. Can anyone hint at what my next step should be or the point at which I should scrap the work that follows and start with a new direction? The section of my textbook this is from is on Chinese Remainder Theorem, so I am positive that I need to apply it in that second half of the proof; I am just not sure how to get to that point.


Can I take and say that by Chinese Remainder Theorem for $a_i'=a_i/d_i$, $b_i'=b_i/d_i$, $n_i'=n_i/d_i$, and $(a_i')^{-1}$ as defined above, there exists an integer $z$ such that $z \equiv (a_i')^{-1}b_i' \mod n_i'$ for $i = 1,\dots,n$, and so $a_i'z \equiv b_i' \mod n_i'$. Then by multiplying through by $d_i$, $a_iz \equiv b_i \mod n_i$, thus completing the proof? I am a bit weary of this due to just scrapping all the $p_i$.

  • 1
    $\begingroup$ I'd write $s_i$ rather than $s$, so you don't imply the same $s$ works for each triple $(a_i,b_i,n_i)$. $\endgroup$ Aug 17, 2013 at 19:29
  • $\begingroup$ @ThomasAndrews Thanks for pointing that out, made the edit. $\endgroup$
    – Alex
    Aug 17, 2013 at 19:31
  • $\begingroup$ Funny thing was, your answer got the hard part first. I was actually trying all the $a_i/d_i$ stuff to get the equivalent of $p_i$ before I realized your answer had a simple way to find the $p_i$... $\endgroup$ Aug 17, 2013 at 19:50
  • $\begingroup$ @ThomasAndrews Yeah, I was sitting there looking at it like... ok... I know all my $p_i$ have to be $z$, but how do I know they are all the same? I didn't think about taking the solution to their congruence with CRT like you pointed out even though I knew I should be using CRT somewhere. $\endgroup$
    – Alex
    Aug 17, 2013 at 20:09

1 Answer 1


For $\Leftarrow$: Once you've got the $a_ip_i\equiv b_i\pmod {n_i}$, you can just solve $z\equiv p_i\pmod {n_i}$ using Chinese Remainder theorem, and you are done.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .