1. ## Congruences

Here is the question I am having trouble with:

Find the remainder when 5^183 is divided by 99.

Any help is appreciated.

2. Originally Posted by Shapeshift
Here is the question I am having trouble with:

Find the remainder when 5^183 is divided by 99.

Any help is appreciated.
Hint $(5,99)=1,183\text{ mod }\phi(99)=3$

3. Hi, I understand that the gcd of those numbers is 1. However, I don't quite understand your hint about the euler phi function, because my teacher hardly taught this. If you could help me understand it that would be great

4. Originally Posted by Shapeshift
Hi, I understand that the gcd of those numbers is 1. However, I don't quite understand your hint about the euler phi function, because my teacher hardly taught this. If you could help me understand it that would be great
Euler's theorem states that if $(a,n)=1$ then $a^{\phi(n)}\equiv 1\text{ mod }n$. So, since $(5,99)=1$ we see that $5^{183}=5^{3+3\cdot 60}=5^3\cdot \left(5^{\phi(99)}\right)^3\equiv 5^3\text{ mod }99$