Group Theory - Cyclic Groups & Inverses A few months ago I correctly wrote that the cyclic subgroups of $(\{1,2,4,8\},\times_{15})$ were
\begin{align}
<1> &= \{1\}\\
<2> &= \{1,2,4,8\} = <2^{-1}>=<8>\\
<4> &= \{1,4\}
\end{align}
I have forgotten how I identified that 8 was the inverse of 2, without actually generating the group. (I remember using Cayley tables initially, then discovering an easy way to do it - but it's gone).
Could someone remind me a quick / easy way to do this please?
Many thanks,
John
 A: Note that you want $2x\equiv 1$ mod $15$. $15+1=16$ is a multiple of $2$, and $\frac {16}2=8$.

In response to the comment below, I've expanded the answer to illustrate some more general aspects. In general suppose we are working modulo $n$ and we want to find the multiplicative inverse of $m$ which is co-prime to $n$ (if $m,n$ have a non trivial common factor there is no inverse).
The Euclidean Algorithm for finding the highest common factor of $m$ and $n$ gives us integers $r, s$ with $rm+sn=1$. Modulo $n$ this becomes $rm\equiv 1$ and $r$ is the inverse we were looking for.
In easy cases it is just as easy to check $1, n+1, 2n+1, 3n+1, \dots (m-1)n+1$ for divisibility by $m$ - since this also gives the inverse.
So with $9$ mod $32$, try $1,33,65, \dots$ - but note that you have to add $96$ to $33$ before you get another multiple of $3$, so you only have to test $33, 129, 225 \dots$ and $225=9\times 25$.
The other way goes:
$32=3\cdot 9+5$
$9=1\cdot 5+4$
$5=1\cdot4+1$
Now reverse:
$$1=5-4=5-(9-5)=2\cdot 5-9=2\cdot(32-3\cdot9)-9=2\cdot32-7\cdot9$$ So the inverse of $9$ is $-7\equiv 25$.
A: $2 \cdot 8 = 16 \equiv 1$ (mod $15$)
