Last 12 digits of 123456789^987654321

This is an excellent example of where "Exponentiation by squaring" can be used. The key here is that:

$x^n = x (x^2)^{\frac{n-1}{2}}$ , if n is odd

and

$x^n = (x^2)^{\frac{n}{2}}$ , if n is even

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

base = 123456789
exp = 987654321
modulo = pow(10,12)
res = 1

def fastExp(x,n):
    if( n == 0 ): 
        return 1
    elif(n == 1): 
        return x
    elif(n%2==0): 
        return fastExp(x*x % modulo, n/2)
    else:         
        return ( x * fastExp(x*x % modulo, (n-1)/2) ) % modulo

print fastExp(base, exp)

I suppose this is very certainly not the intended solution:

1
2

print(pow(123456789, 987654321, 1000000000000)) # pow is built-in
# prints 132974933589

Which just means we can just re-implement exponentiation by squaring :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def pow(base, exponent, modulo):
    # base case: integer raised to the 0th power is 1. yes, 0^0 = 1
    if exponent == 0: return 1 % modulo
    # to compute a^n, we compute a^(n//2) and square it
    # this is why the function is fast (logarithmic time)
    temporary = pow(base, exponent // 2, modulo)
    result = (temporary * temporary) % modulo
    # if the exponent is odd, we only have a^(n-1); multiply by a
    if exponent % 2 == 1: result = (result * base) % modulo
    # return the result
    return result

print(pow(123456789, 987654321, 1000000000000))
# prints 132974933589

MATHEMATICA ONE-LINER : PowerMod[123456789,987654321,10^12]

123456789 = 3 $\times$ 3 $\times$ 3607 $\times$ 3803

123456789 for String_9;

Grouped as 3 $\times$ 3607, and 3 $\times$ 3803 respectively for String_12;

With 18 S.F. calculations, 132974933589 is derived from _ 974933589, 801066457221 and 475687966609 for 381057674154132974933589.

123456789 based for 974933589;

10821 based for 801066457221 and

11409 based for 475687966609.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

[1]   
     product:=123456789.0;
     i:=2;
     Z:
         product:=Cut9(product*123456789.0);
         INC(i);
         IF i>987654321 THEN
            GOTO V;
     GOTO Z;
     V:

[2]
     product:=1.0;
     i:=1;
     Z:
         product:=Cut12(product*10821.0);
         INC(i);
         IF i>987654321 THEN
            GOTO V;
     GOTO Z;
     V:

[3]
     product:=1.0;
     i:=1;
     Z:
         product:=Cut12(product*11409.0);
         INC(i);
         IF i>987654321 THEN
            GOTO V;
     GOTO Z;
     V:

It took few hours to complete evaluations by computer with faster routines.

Answer: $\boxed{132974933589}$

This a solution in python 3.4 that not use recursive function.

1
2
3
4
5
6
7
8
9

def solve(base, exp, mod):
    "Last 12 digits of 123456789^987654321"
    res = 1
    while exp > 0:
        if exp%2 == 1 : res = (res*base)% mod
        base = (base * base )%10**12
        exp = exp // 2      
    return res
print(solve(123456789, 987654321,10**12 ))