Project Euler/97

This is problem 97 on Project Euler: https://projecteuler.net/problem=97

Overview of the Problem

Question

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^6972593 − 1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p − 1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433 × 2^7830457 + 1.

Find the last ten digits of this prime number.

Why this problem

This problem is a classic exercise in modular arithmetic. The prime number in question has over two million digits, making it impossible to compute directly using standard integer types. The key insight is that only the last ten digits are required, which means we can work entirely modulo 10¹⁰. This problem demonstrates the power of modular exponentiation — specifically, the technique of exponentiation by squaring (also known as binary exponentiation) — to efficiently compute enormous powers under a modulus.

Solution Approach

Mathematical Reduction

Let the number in question be:

$ N = 28433 \times 2^{7830457} + 1 $

We are asked for the last ten digits of N, which is equivalent to computing:

$ N \bmod 10^{10} $

Because congruences respect both multiplication and addition, we can reduce the power first:

$ N \equiv 28433 \times \left( 2^{7830457} \bmod 10^{10} \right) + 1 \pmod{10^{10}} $

If we define:

$ P \equiv 2^{7830457} \pmod{10^{10}} $

then the answer is simply:

$ (28433 \times P + 1) \bmod 10^{10} $

The entire problem reduces to computing one value: the residue of 2^7830457 modulo 10¹⁰.

Binary Exponentiation (Exponentiation by Squaring)

The exponent 7830457 is large (it would produce over 2.3 million decimal digits if fully expanded), but it has only 23 binary digits. Binary exponentiation processes the exponent by repeated halving, requiring only about $ \lfloor \log_2 7830457 \rfloor + 1 = 23 $ iterations.

The algorithm maintains three values:

• result r (initialized to 1)
• base b (initialized to 2 mod 10¹⁰)
• exponent e (initialized to 7830457)

At each step:

1. If e is odd, multiply r by b (modulo 10¹⁰)
2. Square b (modulo 10¹⁰)
3. Halve e (integer division by 2)

The loop invariant is:

$ r \times b^{e} \equiv 2^{7830457} \pmod{10^{10}} $

When the loop terminates (e = 0), the accumulated result r is exactly the desired residue P.

Why Not Euler's Theorem?

The modulus is $ 10^{10} = 2^{10} \times 5^{10} $. Since the base (2) shares a common factor with the modulus, $ \gcd(2, 10^{10}) = 2 \neq 1 $, Euler's theorem cannot be applied directly to reduce the exponent modulo $ \varphi(10^{10}) $. The robust approach of repeated squaring with modular reduction at every step works regardless.

Complexity

Binary exponentiation uses $ O(\log e) $ modular multiplications. With only ~23 iterations and at most one extra modular multiplication per iteration, the algorithm is extremely fast. Memory usage is $ O(1) $ — only a handful of integers are stored, and each is immediately reduced modulo 10¹⁰.

Java Solution

The Java implementation uses java.math.BigInteger for arbitrary-precision arithmetic, specifically leveraging the built-in modPow() method which implements binary exponentiation natively.

import java.math.BigInteger;

public class Problem097 {
    public static void main(String[] args) {
        BigInteger MOD = BigInteger.TEN.pow(10);

        // Compute 2^7830457 mod 10^10 using built-in modular exponentiation
        BigInteger powerOfTwo = BigInteger.valueOf(2)
            .modPow(BigInteger.valueOf(7830457), MOD);

        // Apply the formula: (28433 * powerOfTwo + 1) mod 10^10
        BigInteger result = powerOfTwo
            .multiply(BigInteger.valueOf(28433))
            .add(BigInteger.ONE)
            .mod(MOD);

        // Print with leading zeros to ensure exactly 10 digits
        System.out.println(String.format("%010d", result));
    }
}

Explanation of the Code

1. Modulus setup: BigInteger.TEN.pow(10) creates the modulus 10¹⁰ = 10000000000.
2. Modular exponentiation: BigInteger.valueOf(2).modPow(BigInteger.valueOf(7830457), MOD) computes 2^7830457 mod 10¹⁰ using the JVM's highly optimized binary exponentiation.
3. Apply the formula: Multiply by 28433, add 1, and reduce modulo 10¹⁰ one final time.
4. Format output: String.format("%010d", result) ensures the output is zero-padded to exactly 10 digits (the leading digits could be zeros, and they must be included).