# Prove that there exist $r, s \in \mathbb{Z}$ such that det $\begin{pmatrix} a & b \\ r & s \end{pmatrix} \in \mathbb{Z}_n^{\times}$

Suppose $(a,b) \in \mathbb{Z}_n \times \mathbb{Z}_n$ has order $n$.

Prove that there exist $r, s \in \mathbb{Z}$ such that det $\begin{pmatrix} a & b \\ r & s \end{pmatrix} \in \mathbb{Z}_n^{\times}$

I took linear algebra a long time ago and don't really remember any of it. Am I right that what I what to show is that $as - rb \neq 0$, which I can rephrase as $as \not\equiv rb \pmod{n}$?

Is it valid just to let $s = a$ and $r = b$, then for it to fail $a\cdot a \equiv b \cdot b \pmod{p}$, which can't be true because in a previous part of this problem I showed $\gcd(a,b,n) = 1$

• Hint: Show $(a.b)$ has order $n$ if and only if $\gcd(a.b,n)=1$. – Thomas Andrews Apr 12 '18 at 5:13
• @ThomasAndrews I've actually already done that. I'm struggling on how to bring that into play – XRBtoTheMOON Apr 12 '18 at 5:15
• You want to show $as-rb$ is a unit $\mathbb Z_n$, not that it is non-zero. – Thomas Andrews Apr 12 '18 at 5:16
• @ThomasAndrews ahh yes, oops, I forgot $n$ isnt necessarily prime – XRBtoTheMOON Apr 12 '18 at 5:20

## 1 Answer

$\mathbb Z_{n}^{\times}$ is not the non-zero elements of $\mathbb Z_n$, it is the units of $\mathbb Z_n.$

Part 1: Show that $(a+n\mathbb Z,b+n\mathbb Z)$ has order $n$ if and only if $\gcd(a,b,n)=1.$

Part 2: Now, if $\gcd(a,b,n)=1$ then we can find $x,y,z$ so that $ax+by+nz=1$. So you can chose $(r,s)=(x,-y)$ then $ar-bs = 1-nz.$