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

  • 1
    $\begingroup$ Hint: Use Chinese remainder theorem. $\endgroup$
    – Hanul Jeon
    Jan 14, 2013 at 14:19

2 Answers 2


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


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .