# Computing $\langle 3,5\rangle$ in $U_{16}$

I seek to compute $\langle 3,5\rangle$ in $U_{16} = \{a \in \mathbb{Z}_{16} : \gcd(a,16)=1\}$ under multiplication mod 16, but my book only explains how to compute single-element generators. I know that $\langle a\rangle = \{a^k : k\in \mathbb{Z}\}$, but I also know that $U_{16}$ is not cyclic, so $\langle a,b\rangle \neq \{a^nb^m:n,m\in \mathbb{Z}\}$. It'd be great if I can see how the first few elements are generated and see how that was done so that I can fill in the rest.

EDIT: I got that $\langle 3,5 \rangle = U_{16}$. Is this correct?

• Basically, you need to go poking around and multiply everything by everything until you stop getting new elements. Oct 4, 2016 at 10:38
• That seems tedious! I computed <3> and <5> and generated 1, 3, 5, 9, 11, and 13. $U_{16}$ contains those as well as 7 and 15, so can I stop if I manage to generate both? Also, what are $3^{-1}$ and $5^{-1}$ in this case? Oct 4, 2016 at 10:44
• Since $\;U_{16}\cong\Bbb C_2\times C_4\;$, you're going to get a subgroup of this direct product. But both $\;3,5\;$ are elements of order four... Oct 4, 2016 at 10:45
• Apologies DonAntonio, but that response is way above my head. I didn't know that those are congruent (and thus I don't know why that's the case). I also don't know what $C_4$ is. How does 3 and 5 being elements of order 4 help in computing the set they generate? Oct 4, 2016 at 10:50
• It doesn't. (Not that much, and not that simple, at least.) Keep poking around. There can't be a subgroup of 6 elements, so if you have 6 of them, you can safely assume you'll have all 8 in the end. Also, keep track of the cases when you're getting 1 as a product; that will help you to locate $3^{-1}$ and $5^{-1}$. Oct 4, 2016 at 11:09

First of all consider the subgoup $H$ generated by $3$, as you have already done. We have $H = \{3^0, 3^1,3^2,3^4\} = \{1,3,9,11\}$. A coset (the only one) can be obtained by multiplying the elements of $H$ with an element not belonging to it, take $5$. This gives $H_5 = \{3^05, 3^15,3^25,3^45\}=\{5,15,13,7\}$. This shows that every element of $U_{16}$ can be written in a unique way as $3^i5^j$ with $i \in \mathbb{Z}_4$ and $j \in \mathbb{Z}_2$. This proves $U_{16} = \mathbb{Z}_4 \times \mathbb{Z}_2 = \left\langle 3, 5 \right\rangle$.