How to solve $ x = 5^{1345}\bmod 58$? Fermat's little theorem

Question

$ x = 5^{1345}\bmod 58$.

I wrote a program that finds and period of residues and builds a table. This table consists of $k$ lines where $k$ is a number of residues in one repeating block, as residues repeat periodically. In other words, I represent this equation as $x = 5^{n \cdot k+m} \bmod 58$, where $m$ is # of residue in table, and that residue is the answer.

But how to solve this equation mathematically? This algorithm is too complicated to be done on paper. I know that it's possible to use Fermat's little theorem here, but can't understand how. Hope someone will help me to understand this.

Answer 1

$5^{1345} = 5 \cdot 5^{1344} = 5 \cdot (5^{28})^{48} = 5 \cdot (5^{\phi(58)})^{48} = 5 \cdot 1^{48} = 5 \mod 58$.

Answer 2

Use Euler's theorem to get that: $$5^{28}\bmod{58} =1$$ And use: $$5^{1345}\bmod{58} = 5^{48\cdot28+1}\bmod{58}=5\cdot 1^{48}=5$$