0

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?

4pie0
  • 29,204
  • 9
  • 82
  • 118
user2266603
  • 103
  • 1
  • 3
  • 9
  • Divide both the dividend and the divisor by 3 and you'll get a prime divisor. – Petr Skocik Feb 10 '14 at 12:32
  • 45 (I really hoped it would be 42). http://ideone.com/mpZKuj – Henrik Feb 10 '14 at 14:01
  • possible duplicate of [Calculate the modulus of a number at a certan power (the number at that power is quite big)](http://stackoverflow.com/questions/5433992/calculate-the-modulus-of-a-number-at-a-certan-power-the-number-at-that-power-is) – John Alexiou Feb 10 '14 at 14:02
  • Also look at http://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n – John Alexiou Feb 10 '14 at 14:03
  • 3
    This question appears to be off-topic because it is about mathematics and not programming. Try math.stackexchange.com. – interjay Feb 10 '14 at 14:28

2 Answers2

2

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.

4pie0
  • 29,204
  • 9
  • 82
  • 118
1

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))

Vikram Bhat
  • 6,106
  • 3
  • 20
  • 19
  • have you written it by yourself or maybe can you provide a link to math derivation? – 4pie0 Feb 11 '14 at 11:42
  • @piotruś i have written by myself as used it in RSA . Here is link for proof http://en.wikipedia.org/wiki/Modular_exponentiation – Vikram Bhat Feb 11 '14 at 11:45