### How do I calculate the remainder for extremely large exponential numbers using Java?

This StackOverflow question asks

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

I though the answer was worth reproducing as there is a surprisingly simple solution.

An answer is to modulus the value in each iteration of calculating the power

``````(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``````

1. Hi, how did you colorize the Java code? I see that the formulas given are not colorized -- how are they formatted? The reason I ask is that I'm interested in writing a blog which will have some code in it, so I'm looking around to see how other blogs have displayed code. Thanks for any info.