Im struggling with an example excercise because I have problemes to comprehend an step in the calculation
$3^{36} \mod 59 = 3^{7} \mod 59$
How can I reduce the exponent $36$ to $7$? I tried it with fermats theorem, but that didn't helped me at all(at least, I didn't know how..)
It is not immediately obvious, but follows after a while by Fermat's Theorem.
By Fermat's Theorem, we have $3^{58}\equiv 1\pmod{59}$. That is certainly not enough. But in fact $3^{29}\equiv 1\pmod{59}$, because $3$ is a quadratic residue of $59$. This can be verified by Reciprocity, or more simply by noting that $11^2\equiv 3\pmod{59}$. It follows that $3^{29}\equiv 11^{58}\equiv 1\pmod{59}$.
Thus $3^{29+7}\equiv 3^7\pmod{59}$.