# Modular Exponentiation

• Sep 13th 2010, 05:24 PM
matt.qmar
Modular Exponentiation
Hello,

I can't recall how to deal with large exponents in modular arithmetic.

Specifically, the question is to determine the value of 8^402 mod 5.

It is equivalent to (2^402 mod 5)^3 (since 2^3=8) from what I recall, but not sure how that helps...

Thanks!
• Sep 13th 2010, 05:31 PM
undefined
Quote:

Originally Posted by matt.qmar
Hello,

I can't recall how to deal with large exponents in modular arithmetic.

Specifically, the question is to determine the value of 8^402 mod 5.

It is equivalent to (2^402 mod 5)^3 (since 2^3=8) from what I recall, but not sure how that helps...

Thanks!

Here because 5 is prime we can use Fermat's Little Theorem and in general we can use Euler's theorem (which requires gcd of the base and the modulus to be 1).

So it's $8^{402}\equiv 3^{2}\equiv 4\pmod{5}$.