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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.