# Checking whether two elements in $\mathbb{Z}_N \oplus \mathbb{Z}_N$ generate the whole group

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.

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