Chinese Remainder Theorem and matrix In $\operatorname{SL}_2\left(\Bbb Z\right)$, theorem 3.2 in p.5, it states that (for an integer $N$ such that $(a,b,N) = 1$) there exists a $b' \equiv b \pmod{N}$ such that $(a,b')=1$ and can be done by using CNT. But I can't do this. I write $N=p_1^{e_1}\cdots p_k^{e_k}$ and use the fact that $(p_i^{e_i},p_j^{e_j})=1$ for $i \not= j$, and try to use CNT, but I don't know how to deal with the part "such that $(a,b')=1$," please help.
 A: The key idea is the following simple
Theorem $\,\ \ b+c\ $ is coprime to $\ a\:$ if every prime factor of $\,a\,$ divides $\,b\,$ or $\,c,\,$ but not both.
Proof $\ $ If not, then  $\,a\,$ and $\,b+c\,$ have a common prime factor $\,p.\,$ By hypothesis $\,p\mid b\,$ or $\,p\mid c.\,$ Wlog, say $\,p\mid c.\,$ Then $\,p\mid (b+c)-c = b,\,$ so $\,p\,$ divides both $\,b,c,\,$ contra hypothesis. $ $ QED
Since we seek $\,b+nc\,$ coprime to $\,a,\,$ it suffices to choose $\,c\,$ such that each prime factor $\,p\,$ of $\,a\,$ divides exactly one of $\,b\,$ or $\,nc.\,$ Note $\,p\,$ can't divide both $\,b,n,\,$ else $\,p\mid a,b,n,\,$ contra hypothesis. Therefore it suffices to choose $\,c\,$ to be the product of primes in $\,a\,$ that do not occur in $\,b\,$ or in $\,n.\,$ 
This method of generating (co)primes by partitioning the prime factors of $\,a\,$ into two summands has an illustrious history, e.g. Stieltjes used it to generalize Euclid's classical proof that there are infinitely many primes: split the product $\: a\,$ of the prior primes into two products $\,b,c.\,$ Their sum yields an integer coprime to the prior primes, so its prime factors are new, i.e. not among the prior primes. Euclid's classic proof is simply the special case where $\, c = 1.$
A: Concretely:
Take $x$ to be the product of all prime factors of $a$ which do not divide $b$ and set $b' = b +xN$.
Note that $(a,b,N) = 1$.
Then for any prime $p$ dividing $a$, there are two cases:


*

*If $p$ divides $b$, then it cannot divide $N$ as $(a,b,N) = 1$, and by definition it doesn’t divide $x$, so it does not divide $xN$ and therefore it doesn’t divide $b' = b + xN$.

*If $p$ does not divide $b$, then it divides $x$, so it cannot divide $b' = b + xN$.
Therefore there is no prime dividing $a$ and $b'$, so $(a,b') = 1$.
And of course you have $b' \equiv b \mod N$, since $b' = b + xN$.

Now, using the Chinese Remainder Theorem:
Since $(a,b,N) = 1$, by the Chinese Remainder Theorem, there is an $b' ∈ ℤ$ solving $b' \equiv b \mod N$ and $b' \equiv 1 \mod p$ for every prime factor $p$ of $a$ not dividing $N$.
Now, for any prime $p$ dividing $a$, there are two cases:


*

*If $p$ does not divide $N$, then $b' \equiv 1 \mod p$, so $p$ is no prime factor of $b'$.

*If $p$ divides $N$, then – as $(a,b,N) = 1$ – it cannot divide $b$, so by $b' \equiv b \mod N$ it cannot divide $b'$.


So there is no prime dividing $a$ and $b'$.
