modulusnumber-theorymodular-arithmetic

Division with modulus remainders

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?

Solution

  • 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