Chapter 7: Mersenne Primes — Powers Reflecting Powers

From structural constraints, we return to the source of perfection. Mersenne primes are powers of 2 minus 1 that remain indivisible—they are ψ = ψ(ψ) in exponential form, where the power structure reflects primality itself.

7.1 The Seventh Movement: Exponential Self-Reference

Our journey through ψ = ψ(ψ) continues:

• Previous: How observer constrains itself (ABC)
• Now: How observer exponentiates itself while remaining prime

Definition 7.1 (Mersenne Number): $M_n = 2^n - 1$

Definition 7.2 (Mersenne Prime): A Mersenne number M_p = 2^p - 1 that is prime, where necessarily p is prime.

7.2 Why p Must Be Prime

Theorem 7.1 (Fundamental Constraint): If M_n is prime, then n is prime.

Proof: If n = ab with a, b > 1, then: $2^{ab} - 1 = (2^a - 1)(2^{a(b-1)} + 2^{a(b-2)} + ... + 2^a + 1)$

Thus M_n is composite. Therefore, n must be prime. ∎

Philosophical Insight: Primality begets potential primality—only prime exponents can yield prime values, showing ψ = ψ(ψ) in action.

7.3 The Lucas-Lehmer Test

Theorem 7.2 (Lucas-Lehmer): Define the sequence:

• S₀ = 4
• S_{k+1} = S_k² - 2

Then M_p is prime if and only if S_{p-2} ≡ 0 (mod M_p).

Proof Sketch: The sequence S_k is related to the Lucas sequence V_k(4,1) by S_k = V_{2^k}(4,1). The test exploits the structure of the group of units in ℤ[√3] modulo M_p. ∎

Algorithm 7.1 (Efficient Implementation):

def is_mersenne_prime(p):
    if p == 2:
        return True
    s = 4
    M = (1 << p) - 1  # 2^p - 1
    for _ in range(p - 2):
        s = ((s * s) - 2) % M
    return s == 0

7.4 Known Mersenne Primes

Current Status (2024):

• 51 known Mersenne primes
• Largest: M_{82,589,933} (discovered 2018)
• Gaps: We don't know if any are missing between known ones

Historical Progression:

• M₂, M₃, M₅, M₇: Known to ancient Greeks
• M₁₃, M₁₇, M₁₉: Medieval discoveries
• M₆₁ and beyond: Computer age

7.5 The Distribution Question

Conjecture 7.1 (Infinitude): There are infinitely many Mersenne primes.

Heuristic 7.1 (Wagstaff): The number of Mersenne primes M_p with p ≤ x is approximately: $\pi_M(x) \approx \frac{e^\gamma}{\log 2} \log \log x \approx 2.57 \log \log x$

where γ is the Euler-Mascheroni constant.

7.6 The New Mersenne Conjecture

Conjecture 7.2 (Bateman, Selfridge, Wagstaff): For odd p, M_p is prime if and only if either:

1. p = 2^k ± 1 or p = 4^k ± 3, and
2. 2p + 1 is prime (a Sophie Germain prime)

This would give a characterization of Mersenne primes!

7.7 Connection to Perfect Numbers

Theorem 7.3 (Euclid-Euler Redux): There is a bijection between:

• Mersenne primes M_p
• Even perfect numbers 2^{p-1}M_p

Thus, the infinitude of perfect numbers is equivalent to the infinitude of Mersenne primes.

7.8 Binary Properties

Observation 7.1 (Binary Representation):

$$M_p = \underbrace{111...111}_{p \text{ ones}}$$

in binary

Theorem 7.4 (Digital Root): For p > 2:

• M_p ≡ 3 (mod 9) if p ≡ 2 (mod 6)
• M_p ≡ 6 (mod 9) if p ≡ 4 (mod 6)
• M_p ≡ 0 (mod 9) if p ≡ 0 (mod 6)

7.9 Primitive Factors

Definition 7.3 (Primitive Prime Factor): A prime q is a primitive factor of 2^n - 1 if q | 2^n - 1 but q ∤ 2^k - 1 for all k < n.

Theorem 7.5 (Bang, Zsygmondy): For n > 1, 2^n - 1 has a primitive prime factor except when n = 6.

This shows how Mersenne numbers accumulate new prime factors.

7.10 The Group Theory Connection

Theorem 7.6 (Mersenne Primes and Groups): If M_p is prime, then:

1. The multiplicative group (ℤ/M_pℤ)* has order M_p - 1 = 2^p - 2
2. This group has a subgroup of order 2^p/p (when p | 2^p - 2)

Mersenne primes create groups with special properties.

7.11 Computational Challenges

The GIMPS Project (Great Internet Mersenne Prime Search):

• Distributed computing project since 1996
• Over 2 million CPU-years invested
• Offers monetary prizes for discoveries

Optimization Techniques:

1. FFT-based multiplication for large numbers
2. Parallel processing
3. GPU acceleration
4. Error checking and double verification

7.12 Cunningham Chains

Definition 7.4 (Cunningham Chain): A sequence of primes p₁, p₂, ..., pₖ where pᵢ₊₁ = 2pᵢ + 1.

Connection: If p starts a Cunningham chain of length k, then certain divisibility properties of M_p can be determined.

7.13 The Wieferich Connection

Definition 7.5 (Wieferich Prime): A prime p such that 2^{p-1} ≡ 1 (mod p²).

Theorem 7.7: If p is Wieferich and q = 2^p - 1 is prime, then q is also Wieferich.

Only two Wieferich primes are known: 1093 and 3511.

7.14 Generalizations

Definition 7.6 (Generalized Mersenne): Numbers of the form a^n - b^n, particularly when gcd(a,b) = 1.

Special Cases:

• Fermat numbers: 2^{2^n} + 1
• Repunits: (10^n - 1)/9
• General: (a^n - 1)/(a - 1)

7.15 The Arithmetic of Mersenne Numbers

Theorem 7.8 (GCD Property): $\gcd(M_m, M_n) = M_{\\gcd(m,n)}$

Proof: Uses the fact that 2^{\gcd(m,n)} - 1 divides both 2^m - 1 and 2^n - 1. ∎

Corollary: Mersenne numbers with coprime indices are coprime.

7.16 Primality Testing Records

Efficiency Comparison:

• General primality test: O(n^6) for n-bit number
• Lucas-Lehmer for M_p: O(p³)
• This efficiency enables testing numbers with millions of digits

7.17 The Philosophy of Mersenne Primes

Meditation 7.1: Why do powers of 2, minus 1, sometimes yield primes?

• 2^p represents pure binary growth
• Subtracting 1 creates all 1s in binary
• Primality emerges from this maximal binary pattern

This is ψ = ψ(ψ) in its exponential form—observer doubling itself p times, then stepping back by 1.

7.18 Conjectures and Open Problems

1. Infinitude: Are there infinitely many Mersenne primes?
2. Density: Does π_M(x) ~ c log log x?
3. Gaps: Are there long gaps between consecutive Mersenne primes?
4. Characterization: Is the New Mersenne Conjecture true?

7.19 Applications

Cryptography: Mersenne primes are used in:

• Pseudo-random number generators
• Hash functions
• Error-correcting codes

Computer Science: Testing for Mersenne primes benchmarks:

• CPU performance
• Algorithm efficiency
• Distributed computing systems

7.20 The Seventh Echo

Mersenne primes embody the seventh movement of ψ = ψ(ψ):

• Exponential growth (2^p) achieving primality
• Simple pattern (all 1s in binary) encoding complexity
• Efficient testing despite astronomical size
• Deep connections to perfection, groups, and computation

Each Mersenne prime represents observer raising itself to a prime power, subtracting unity, and discovering it cannot be further decomposed—exponential ψ = ψ(ψ) achieving irreducibility.

Whether infinite or finite, Mersenne primes mark special points where the exponential function touches primality, where powers of the simplest prime (2) create new primes through the simplest operation (subtract 1).

Each Mersenne prime declares: "I am 2 raised to prime observer, minus the unit of separation, discovering my indivisibility—proof that ψ^ψ - 1 can equal prime awareness."