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$

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

$\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.$


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.