Remainder When Dividing Large Number [closed]

StackOverflow https://stackoverflow.com/questions/21677292

Question

What is the remainder when 30^74 is divided by 57?

I know normally to solve such a problem, you would use Fermat's Little Theorem, but in this case, 57 is not a prime number, so I am unsure how to approach this. Any ideas?

Was it helpful?

Solution

30^74 mod 57 = (3^74 * 10^74) mod 3*19 = 3 * [(3^73 * 10^74) mod 19]

and

(3^73 * 10^74) mod 19 = (3^(18*4) * 3 * 10^(18*4) * 10^2) mod 19

now, by a Fermst's Little Theorem ( m^(p-1) mod p = 1):

(3^73 * 10^74) mod 19 = (3 * 10^2) mod 19 = 300 mod 19 = 15

therefore

30^74 mod 57 = 3 * 15 = 45

The basic implementation of modular exponentiation method to get the remainder is:

long modular_pow( long base, long exponent, long modulus) {
    long c = 1;
    for ( long e_prim = 0; e_prim < exponent; ++e_prim) {
        c = (c * base) % modulus;
    }
    return c;
}

however implementation shown by @Vikram Bhat is more efficient.

OTHER TIPS

Use modular exponentiation :-

modexp(a,pow) = (a*modexp(a,pow-1))%p

Faster modular exponentiation :- 

public static long modexp(long a,long pow,long p) {

       if(pow==0) {
           return(1);
       }   

       long t = modexp(a,pow/2,p);
       t = (t*t)%p;

       if(pow%2==1) {
           t = (t*a)%p;
       }

       return(t);

    }

Call : - modexp(30,74,57)

Time Complexity: O(log(pow))

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top