This is a rather conceptually simple question. I have a group $\mathbb{Z}_N\oplus\mathbb{Z}_N$ and two distinct elements $b_1$,$b_2$ in this group. These two elements are both of order $N$.

The question I want to ask is whether these two elements allow me to generate the whole group $\mathbb{Z} _N\oplus\mathbb{Z}_N$. I believe this question is equivalent to asking whether the following is false: there exists $n,m\in\mathbb{Z}$ s.t. $b_1^n = b_2^m \neq e$, or alternatively that these two elements generate distinct subgroups within $\mathbb{Z}_N\oplus\mathbb{Z}_N$.

Is there a way to determine this without simply checking all combinations of $0\leq n,m<N$ as mentioned above?

The elements are of the form $b_1=(a^{n_1},a^{n_2})$ and $b_2=(a^{n_2},a^{-n_1})$, where $a$ is a generator for $\mathbb{Z}_N$ and $n_1,n_2 \in \mathbb{Z}$, although this may not be important.

Thanks for any help anyone can provide.

  • $\begingroup$ I'm confused by your notation; did you mean $\mathbb{Z}_n$ for some $n\in\mathbb{N}$? $\endgroup$ – Kevin Long Mar 7 '17 at 16:38
  • $\begingroup$ I was also confused, I assumed that $\mathbb{Z}_N$ was meant so I edited that into the question... $\endgroup$ – Zubin Mukerjee Mar 7 '17 at 16:39
  • $\begingroup$ Yes, that is what I meant. $\endgroup$ – Dat Zr Mar 7 '17 at 16:39

There is a shortcut to determine this using linear algebra. Let me write elements of $\mathbb{Z}_N$ as integers (implicitly to be taken mod $N$), so instead of $(a^{n_1},a^{n_2})$ I will write $(n_1,n_2)$. A group-homomorphism $\varphi:\mathbb{Z}_N\oplus\mathbb{Z}_N\to\mathbb{Z}_N\oplus\mathbb{Z}_N$ is essentially the same thing as a $2\times 2$ matrix $\begin{pmatrix}a & c \\ b & d\end{pmatrix}$ of elements of $\mathbb{Z}_N$ where $\varphi(1,0)=(a,b)$ and $\varphi(0,1)=(c,d)$. Given two elements $x=(a,b)$ and $y=(c,d)$ of $\mathbb{Z}_N\oplus\mathbb{Z}_N$, they generate the entire group iff the homomorphism $\varphi$ as above is surjective. Since $\mathbb{Z}_N\oplus\mathbb{Z}_N$ is finite, $\varphi$ is surjective iff it is injective. That is, $x$ and $y$ generate the entire group iff $\varphi$ is an isomorphism.

But now linear algebra gives us an easy way to determine whether $\varphi$ is an isomorphism: a matrix is invertible iff its determinant is invertible. In this case, that means $\varphi$ is invertible iff the determinant $ad-bc$ is invertible mod $N$: that is, iff $ad-bc$ is relatively prime to $N$. That is, $(a,b)$ and $(c,d)$ generate the entire group iff $ad-bc$ is relatively prime to $N$. In your notation, that means $b_1$ and $b_2$ generate the group iff $-n_1^2-n_2^2$ is relatively prime to $N$, or equivalently iff $n_1^2+n_2^2$ is relatively prime to $N$.

(If you are familiar only with linear algebra over a field, the relevant parts here work just the same over any commutative ring, such as $\mathbb{Z}_N$. For instance, the usual explicit formula for the inverse of a matrix still works, as long as the determinant is invertible in your ring so that you can divide by it.)

  • $\begingroup$ This is exactly what I was looking for, thanks! $\endgroup$ – Dat Zr Mar 7 '17 at 20:10

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.