How do i calculate the remainder for extremely large exponential numbers using java?

Question

How do i calculate the remainder for extremely large exponential numbers using java ? eg. (48^26)/2401

I tried using BIGINTEGER, however it gave the same output for large divisors.I'm not sure if BIG INTEGER can do this .I have tried all other PRIMITIVE data type.They seem to be insufficient.

FYI it tried the following code:

BigInteger a = new BigInteger("48");
a = a.pow(26);
BigInteger b = new BigInteger("2401");//49*49
a = a.mod(b);
System.out.println(a);

I don't know why i got the same output everytime, it's weird that it's working fine now. The answer comes out to be 1128

Answer 1

You can use repeated modulus of smaller numbers.

say you have

(a * b) % n
((A * n + AA) * (B * n + BB)) % n                     | AA = a %n & BB = b % n
(A * B * n^2 + A * N * BB + AA * B * n + AA * BB) % n
AA * BB % n                                           since x * n % n == 0
(a % n) * (b % n) % n

In your case, you can write

48^26 % 2401
(48^2) ^ 13 % 2401

as

int n = 48;
for (int i = 1; i < 26; i++)
    n = (n * 48) % 2401;
System.out.println(n);

int n2 = 48 * 48;
for (int i = 1; i < 13; i++)
    n2 = (n2 * 48 * 48) % 2401;
System.out.println(n2);

System.out.println(BigInteger.valueOf(48).pow(26).mod(BigInteger.valueOf(2401)));

prints

1128
1128
1128

As @Ruchina points out, your example is small enough to calculate using a simple double expression.

for (int i = 1; i < 100; i++) {
    BigInteger mod = BigInteger.valueOf(48).pow(i).mod(BigInteger.valueOf(2401));
    double x = Math.pow(48, i) % 2401;
    if (mod.intValue() != x) {
        System.out.println(i + ": " + mod + " vs " + x);
        break;
    }
}

prints

34: 736 vs 839.0

In other words, any power of 48 is fine up to 33.

Answer 2

This worked for me.

import java.math.BigInteger;


public class BigMod{
        public static void main (String[] args){
                BigInteger b1 = new BigInteger ("48");
                BigInteger b2 = new BigInteger ("2401");
                BigInteger b3 = b1.pow(26);
                BigInteger result = b3.mod(b2);
                System.out.println(result);
        }
}

Not sure what trouble you're having with BigInteger. Can you explain what didn't work?