Solving $x^{45} \equiv 7 \mod 113$ Pretty much as in the title, though a more general answer would also be nice. . I thought you could find in inverse of $45$ in mod $113$, then take the equation to that power. In this situation that gives:
$45^{-1} = 108 \mod 113$
$(x^{45})^{108} \equiv x^{45\times108} \equiv x^1 \equiv 7^{108}$
However this is wrong according to wolfram alpha, so I guess the above is complete nonsense. The correct answer is $83$

$$\text{ Solve $x^{45} \equiv 7 \pmod{113}$}.$$
For all $\gcd(x,113)=1$: $\quad x^{112} \equiv 1 \pmod{113}$
$45 \times 5 \equiv 225 \equiv 2(112) + 1 \equiv 1 \pmod{112}$
$(x^{45})^{5} \equiv x^{225} \equiv x \pmod{113}$ 
$7^3 \equiv 343 \equiv 3(113) + 4 \equiv 4 \pmod{113}$
$7^5 \equiv 7^2 \times 7^3 \equiv 49\times 4 \equiv 196 \equiv 113 + 83 \equiv 83 \pmod{113}$
$x \equiv (x^{45})^{5} \equiv 7^5 \equiv 83$ 
Computing $45^{-1} \pmod {112}$
\begin{array}{r|r|rr|l}
   & 112 &  1 &  0 & 112 = 1(112)+0(45)\\
-2 &  45 &  0 &  1 & 45 = 0(112)+1(45)\\
-2 &  22 &  1 & -2 & 22 = 1(112)-2(45)\\
   &   1 & -2 &  5 & 1 = -2(112)+5(45) 
\end{array}
Since $1 = -2(112)+5(45)$, then $5(45) = 1+2(112) \equiv 1 \pmod{112}$.
