How can I find the residue of this removable singularity? We have the following function : $$f(z)=\frac{z^2}{1-\cos z}$$ where $z_0=0$ is a removable singularity since the limit as $z$ goes to $0$ is $2$. 
In such cases, in order to find the residue I proceed by trying to find the Laurent series around the singularity and checking the coefficient of the $z^{-1}$ term. However, the cosine is in the denominator and I can't properly find the first negative power of $z$. Will I have to resort to a polynomial division to get my negative $z$ powers?

Mark's answer is, of course, the best to approach this. Supposing it were not a removable singularity, then what I'll show will still sometimes work. In specific, you'll get the Laurent Series.
Recall Geometric Series.
$$ \frac{x^2}{1-\cos{x}} = x^2 (1+\cos(x)+\cos(x)^2+\dots) = x^2 \sum_{n=0}^\infty \left( \sum_{k=0}^\infty (-1)^k \frac{x^{2k}}{(2k)!} \right)^n $$ That's your Laurent Series.
