Project Euler/97 - Revision history

Admin: Replace remaining em-dash with regular dash in Complexity section (via update-page on MediaWiki MCP Server)

2026-06-24T11:28:53Z

Replace remaining em-dash with regular dash in Complexity section (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 11:28, 24 June 2026
Line 79:		Line 79:
	The modulus is <math>10^{10} = 2^{10} \times 5^{10}</math>. Since the base (2) shares a common factor with the modulus, <math>\gcd(2, 10^{10}) = 2 \neq 1</math>, Euler's theorem cannot be applied directly to reduce the exponent modulo <math>\varphi(10^{10})</math>. The robust approach of repeated squaring with modular reduction at every step works regardless.		The modulus is <math>10^{10} = 2^{10} \times 5^{10}</math>. Since the base (2) shares a common factor with the modulus, <math>\gcd(2, 10^{10}) = 2 \neq 1</math>, Euler's theorem cannot be applied directly to reduce the exponent modulo <math>\varphi(10^{10})</math>. The robust approach of repeated squaring with modular reduction at every step works regardless.

	~~==Complexity==~~		Binary exponentiation uses <math>O(\log e)</math> modular multiplications. With only ~23 iterations and at most one extra modular multiplication per iteration, the algorithm is extremely fast. Memory usage is <math>O(1)</math> - only a handful of integers are stored, and each is immediately reduced modulo 10<sup>10</sup>.

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

	=Java Solution=		=Java Solution=

Admin: Replace em-dashes with regular dashes (via update-page on MediaWiki MCP Server)

2026-06-24T11:28:46Z

Replace em-dashes with regular dashes (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 11:28, 24 June 2026
Line 13:		Line 13:
	==Why this problem==		==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<sup>10</sup>. 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.		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<sup>10</sup>. 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=		=Solution Approach=

Admin: Create Project Euler/97 page with problem statement, solution approach, and Java solution (via create-page on MediaWiki MCP Server)

2026-06-24T11:21:56Z

Create Project Euler/97 page with problem statement, solution approach, and Java solution (via create-page on MediaWiki MCP Server)

New page

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 26972593 − 1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p − 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 × 27830457 + 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 1010. 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:

<math>
N = 28433 \times 2^{7830457} + 1
</math>

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

<math>
N \bmod 10^{10}
</math>

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

<math>
N \equiv 28433 \times \left( 2^{7830457} \bmod 10^{10} \right) + 1 \pmod{10^{10}}
</math>

If we define:

<math>
P \equiv 2^{7830457} \pmod{10^{10}}
</math>

then the answer is simply:

<math>
(28433 \times P + 1) \bmod 10^{10}
</math>

The entire problem reduces to computing one value: the residue of 27830457 modulo 1010.

==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 <math>\lfloor \log_2 7830457 \rfloor + 1 = 23</math> iterations.

The algorithm maintains three values:

* '''result''' r (initialized to 1)
* '''base''' b (initialized to 2 mod 1010)
* '''exponent''' e (initialized to 7830457)

At each step:

# If e is odd, multiply r by b (modulo 1010)
# Square b (modulo 1010)
# Halve e (integer division by 2)

The loop invariant is:

<math>
r \times b^{e} \equiv 2^{7830457} \pmod{10^{10}}
</math>

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

==Why Not Euler's Theorem?==

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

==Complexity==

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

=Java Solution=

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

<syntaxhighlight lang="java">
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));
}
}
</syntaxhighlight>

==Explanation of the Code==

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

{{ProjectEulerFlag}}

[[Category:Prime Numbers]]
[[Category:Modular Arithmetic]]
[[Category:Number Theory]]