Division with modulus remainders

Question

How can you do division with modulus remainders?

For example: Find the remainder when 9^2012 is divided by 11.

Using modular arithmetic, 9 == 1(mod 4), so 9^2012 == 1^2012(mod 4). Therefore, 9^2012 == 1(mod 4). Also, 11 == 3(mod 4). To answer the question, I'm trying to do 1(mod 4)/3(mod 4). Is there any way to do this?

Answer 1

There two important theories that would help you to solve this problem :-

1. Modular Exponentiation
2. Fermat's little theorem

Modular Exponentiation :- This simple recursive formula to make you understand :-

(a^n)%p = ((a^(n-1))%p*a)%p

The above formula can help you prevent the overflow which occurs if a^n is large. Moreover fast exponention can be done using O(logn)

Fermat's little theorem :- If p is prime in your case 11 is prime then (a^(p-1))%p = 1 for any a that is co-prime to p hence (a^n)%p = (a^(n%(p-1)))%p

your example :-

9^2012 % 11 = ?

11 is prime and 9 is co-prime to 11 then using fermat's theorem

9^2012 % 11 = (9^(2012%10)) % 11
2012%10 = 2

9^2012 % 11 = 9^2 % 11 = 4