Find the multiplicative inverses of all the elements in $\Bbb Z_{16}^\times$ I know the elements in  $\Bbb Z_{16}^\times$ are {1,3,5,7,9,11,13,15}, but I don't know how to find the multiplicative inverses of each element. 
The group is supposed to read "Z16 cross"
 A: Theoretically, you should perform the extended Euclidean algorithm for each of these elements.
In the present case, however, a sensible knowledge of multiplication tables will do. You only need a list of the first multiples of $16$, $+1$.


*

*I'll skip the inverse of $1$. As $15\equiv -1$, you see at once that $15^{-1}=15$.

*$3\cdot 11\equiv 1$.

*The previous inverses show that $(-5)^{-1}\equiv 3$, so $5^{-1}\equiv -3\equiv 13$.

*$7\cdot 7\equiv 1$.

*$9\cdot 9\equiv 1$.

A: To economise a little note that $-x \cdot -y = x\cdot y$ so if $x$ is the inverse of $y$ then $-x$ is the inverse of $-y$ (or $16-x$ is the inverse of $16-y$ if you like). 
You could count the elements as $\pm 1, \pm 3, \pm 5, \pm 7$ to simplify arithmetic too. 
Also note that if $x^n\equiv 1$ then $x\cdot x^{n-1}=1$ so if you can't spot the inverse, raising to a power will get it. And if you get lots of powers, you will at least also have $x^2\cdot x^{n-2}=1$ etc for free.
So $\pm 1$ are obvious. $3^2=-7, 3^3=-5, 3^4=1$ so you get $3\times -5=1$ and $-7\times -7=1$ and that is enough to get all the inverses by changing signs. Then add $16$ to the negative numbers if you want the least positive residues.
A: For every element,  the order divides $8$.  So the order is $1,2,4$ or $8$. You can cross off $8$, as it is known $\mathbb Z_{16}^×$ is not cyclic...  
Let's take $3$ for instance.  The order isn't $1$.  $3^2=9\not=1\pmod{16}$.  So the order isn't $2$.  The order of $3$ is in fact $4$:  $3^4=81\cong1\pmod{16}$.  Therefore $3^3\cong{11}\pmod{16}$ is the inverse.   So $3$ and $11$ are inverses.
Now take $5$.  It's easy to see its order is $4$:  $5^4=625\cong1\pmod{16}$.  Thus $5^3=125\cong{13}\pmod{16}$. Thus $5$ and $13$ are universes.
You can easily check that $15$ is it's own inverse, since $15^2=225\cong1\pmod{16}$.
That leaves $9$ and $7$.  A quick check reveals $9$ is it's own inverse.  As for $7$, we have $7$ with order $2$ also.
Note, you could just multiply each element by each of the others.   Or you could use the Euclidean algorithm... 
A: Another possibility is to use the rule, valid in all rings, that if $n$ is a nilpotent element, say $n^k=0$, then $1-n$ is invertible and the inverse can be read from the factorization familiar to us from e.g. geometric sums/series:
$$
1=1^k-n^k=(1-n)(1+n+n^2+\cdots+n^{k-1}).
$$
So, for example, $3=1-(-2)$, and thus (any even number raised to the fourth power is divisible by sixteen and therefore nilpotent, so $k=4$ here):
$$
3^{-1}=(1-(-2))^{-1}=1+(-2)+(-2)^2+(-2)^3= 1-2+4-8=-5\equiv11\pmod{16}.
$$

This method can be used to calculate inverses modulo any power of two.
A: Since $\phi(16)=8$, it follows by Euler's theorem that $$a^8\equiv_{16}1$$ for every $a\in\Bbb Z_{16}^\times$. Noticing that every $a$ is odd, we can do even better: $$a^4\equiv_{16}1$$ This holds, since $16\mid (2n+1)^4-1=16(n^2+n)^2+8n(n+1)$. 
Say you want to find the inverse of $7$, then you know that $7^4\equiv_{16}7\cdot (7)^3\equiv_{16}1$. So $7^3\equiv_{16}7$, is the inverse of $7$.
A: Easy reminder : any perfect square can be represented as $8k$ or $8k + 1$. 
Now all elements of the group are odds. Hence, their square will be represented as $8k + 1$ form, which shows that every element in that group is idempotent. 
