Congruences

• March 5th 2010, 08:56 AM
Shapeshift
Congruences
Here is the question I am having trouble with:

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

Any help is appreciated.
• March 5th 2010, 08:57 AM
Drexel28
Quote:

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$
• March 5th 2010, 09:46 AM
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 :)
• March 5th 2010, 12:09 PM
Drexel28
Quote:

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$