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$
 A: Hint: $45\cdot 5=2\cdot 112+1$

Solution:
If $$x^{45}\equiv 7\pmod{113}$$ then $$ (x^{45})^5\equiv 7^5\pmod{113}$$ that is $$ (x^{112})^2 x\equiv 83\pmod{113}$$ But $113$ is a prime, so $x^{112}\equiv 1\pmod{113}$ by Fermat, and the result follows.
A: Since $113\in\mathbb{P}$:
(1) $\quad \phi(113) = 112\qquad$($\phi(n)$ is Euler's totient function)
(2) $\quad 7^{112} \equiv 1 \bmod 113\quad$(by Euler's theorem and more specifically Fermat's little theorem)
(3) $\quad 7^{112+1} \equiv 7 \bmod 113$
(4) $\quad 45^{-1} \equiv 5 \bmod 112\quad$(Modular multiplicative inverse)
(5) $\quad 7^5 \equiv 83 \bmod 113$
(6) $\quad 83^{45} = 7 \bmod 113\quad$ (Modular exponentiation)
Since $5 * 45 \equiv 1 \bmod 112$,  $(7^5)^{45} \equiv7^1 \bmod 113$.
A: Once you know that $7^5\cong 83\pmod{113}$, this becomes an easy problem. 
Just raise each side of the congruence to the $5$th power. You get $x^{225}\cong 83\pmod{113}$.
Straight substitution of $1$ for $x^{112}$ (they are equal by lil' Fermat) into ${(x^{112})}^2x\cong 83\pmod{113}$ yields $1^2\cdot x\cong 83\pmod{113}\implies x\cong 83\pmod{113}$.
A: $$\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}$.
A: $113$ is prime, hence the units of $\Bbb Z_{113}$ form a cyclic group under multiplication with order $112$.
Therefore, $\forall x \in \Bbb U(113): x^{112} \equiv 1$.
Therefore, you should be finding $45^{-1} \pmod{112}$ instead of $\pmod{113}$.
