Solving $x^{45} \equiv 7 \mod 113$

Question

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$

Answer 1

$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}$.

Answer 2

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.