zeroes to polynomials in residue rings of Z I'm supposed to find zeroes of $x^{12} -16$ in $\mathbb Z_{17}$, seems simple enough but I just can't seem to make any progress.
I realize of course that we have $X^{12} = -1$ in $\mathbb Z_{17}$, but that doesnt seem to get me anywhere, another option is to write it at $(x^6)^2 = -1$, now $-1$ is a quadratic residue of $u = x^6$, so $(u)^2 = -1$ will have two solutions, $-4$, and $+4$, but now im stuck with $x^6 = \pm 4$, and I feel very unsure about how to move on. How does one do this? What theorems are appropriate?
By some theorem, dont remember which right now, this is supposed to have 4 roots.
EDIT: another idea I had was to use wilson's theorem, but 16! = -1 doesn't seem to suggest any way to continue, now I'm just stuck with $16! = x^{12}$
 A: Since you're only concerned with finding roots in $\mathbb{Z}_{17}$, and $0$ is not a root, you can work in the group of units $\mathbb{Z}_{17}^* \cong \mathbb{Z}_{16}$. Then $x^{12} = -1$ is the same as $x^{24} = 1$, but $x^{12} \ne 1$ (since $-1$ is the unique element of order $2$). But $x^{16} = 1$, so $x^{24} = x^{8}$, and you need only count the elements of order $8$ in $\mathbb{Z}_{16}$, of which there are $\phi(8) = 4$.
It's quick to verify that $2 \in \mathbb{Z}_{17}^*$ is an element of order $8$. But then so is $-2 = 15$. Moreover, the map $x \mapsto x^3$ is an automorphism of $\mathbb{Z}_{17}^*$ (in general, raising to a power coprime to the order is an automorphism of an abelian group), so $2^3 = 8$ is also an element of order $8$. Thus the full set of solutions is $\{2, -2, 8, -8\} = \{2, 8, 9, 15\}$. 
A: This answer might be slightly less practical than the existing ones, but I feel it's worth it to get a deeper understanding of problems like this.
The multiplicative group $(\Bbb Z_{17})^\times$ is cyclic of order $16$, that is, it's isomorphic to the additive group $\Bbb Z_{16}$; let's translate the problem over to the additive group. On the left-hand side, $x^{12}$ becomes $12y$. On the right-hand side, $-1$ is the unique non-identity element of $(\Bbb Z_{17})^\times$ whose square is the identity, so its image under the isomorphism must be the unique non-identity element of $\Bbb Z_{16}$ whose double is the identity $0$ - that element is $8$. So we need to solve the equation $12y=8$ in $\Bbb Z_{16}$, that is, the congruence $12y\equiv8\pmod{16}$. And there are standard methods for that - the solutions are $y=2,6,10,14\pmod{16}$.
How do we translate these solutions back to $(\Bbb Z_{17})^\times$? We need to know the isomorphism explicitly - and that's exactly what primitive roots are for. One can check that $3$ is a primitive root modulo $17$, and so one isomorphism from $\Bbb Z_{16}$ to $(\Bbb Z_{17})^\times$ is given by $x=3^y$. (One could also use this isomorphism to figure out the image of $-1$, if we didn't see the argument in the previous paragraph.) Therefore the solutions to the original problem are $x=3^2,3^6,3^{10},3^{14}$, that is, $x\equiv9, 15, 8, 2\pmod{17}$. (Other isomorphisms give the same set of solutions in different orders.)
The moral: solving $x^a\equiv b\pmod p$ (where $p$ is prime) is equivalent to solving $cy\equiv d\pmod{p-1}$, which is totally algorithmic. Indeed, this is how most theorems about the former (such as the formula for the number of solutions the OP alluded to) are proved in the first place.
A: $0 \equiv 1\!+\!x^{12}\!\!\!\overset{\,\ \ \large \times\, x^4}{\underset{\large x^{16}\,\equiv\,{\color{#c00} 1}}\iff} 0\equiv x^4\!+\!\color{#c00}1\equiv x^4\!\color{#c00}{-2^4}\equiv (x^2\!-\!2^2)(x^2\!-\!(\color{#c00}{-1})2^2)=\!\!\!\!\!\overbrace{(x^2\!-\!2^2)(x^2\!-\color{#c00}{4^2}2^2)}^{\large \rm both\ differences\ of\ squares}\!\!\!\!\!=\,\ldots$
