# How to prove that reduction modulo N is onto

I have already showed that if $\begin{pmatrix}a & b\\c & d\end{pmatrix} \in \operatorname{SL}(2,\mathbb{Z}/N\mathbb{Z})$ then $c$ and $d$ are coprime modulo $N$. Now I have to show that for any $(c,d)$ coprime modulo $N$, there exist $c',d'\in \mathbb{Z}$ such that $c'\equiv c\pmod{N}$, $d'\equiv d\pmod{N}$ and $\gcd(c',d')=1$. The definition I am using of coprime modulo $N$ is: $c$ and $d$ are coprime modulo $N$ if there isn't any $f\neq 0$ in $\mathbb{Z}/N\mathbb{Z}$ such that $fc=fd=0$. If I define for every prime $p_i\mid d$ a $\lambda_{p_i}$ such that $c+\lambda_{p_i}N$ is divisible by $p_i$ then how can I use the Chinese Remainder Theorem to prove this?

Lift $c,d$ to $\mathbb{Z}$ such that $d\neq0$. We will find some $\lambda\in\mathbb{Z}$ such that $c'=c+\lambda N$ is coprime to $d'=d$.
Let $P$ be the product of all primes dividing $d$ and not dividing $N$. Let $Q=\gcd(d,N)$.
$c'$ and $d'$ are coprime if and only if $c'$ is coprime to both $P$ and $Q$.
Let $g=\gcd(c,Q)$ and $f=N/g$. Now $fc,fd$ are integer multiples of $fg\equiv0\pmod{N}$, and since $c,d$ are coprime modulo $N$, we conclude $f\equiv0\pmod{N}$, therefore $g=1$.
Hence $Q$ is coprime to $c$. Furthermore $Q$ divides $N$. Consequently, $Q$ is coprime to $c'=c+\lambda N$ for any choice of $\lambda$. It remains to find some $\lambda$ making $c'$ coprime to $P$.
If $P=1$, then $\gcd(c',P)=1$ follows immediately for any choice of $\lambda$. Now suppose $P>1$. Since $N$ is coprime to $P$, there exists an integer $m$ such that $mN\equiv1\pmod{P}$. Choose $u\in\mathbb{Z}$ coprime to $P$, for example $u=1$, and choose $\lambda\equiv m(u-c)\pmod{P}$. Thus $c'=c+\lambda N\equiv u\pmod{P}$ which makes $c'$ coprime to $P$, and we are done.