Explore BrainMass

Primality of Mersenne Numbers

Determine whether m_13 = 2^13 - 1 = 8191 and m_23 = 2^23 -1 = 8388607 are prime.

© BrainMass Inc. brainmass.com July 18, 2018, 10:26 pm ad1c9bdddf

Solution Preview

You can use Fermat's little theorem, which states that:

y^(q - 1) Mod q = 1

where q is a prime and y has no divisor in common with q (we can also say that y is not equal to zero modulo q) . Let me know if you are not familiar with modular arithmetic and don't know what "mod" means.

Suppose that we have some Mersenne number

M_p = 2^p - 1

with p an odd prime. Also, we assume that M_p is not prime. Then we use Fermat's little theorem to find a constraint that any prime divisors of M_p must satisfy. Before we derive this, let's first explain how we are going to use that constraint. We compute M_p Modulo the primes satisfying the constraint to see if one of them divides M_p. We know that:

M_p is not prime -----> There is a prime satisfying the constraint that divides M_p

This is equivalent to:

NOT[There is a prime satisfying the constraint that divides M_p] ----------> NOT[M_p is not prime]

which we can rewrite as:

No primes satisfying the constraint divide M_p ...

Solution Summary

A detailed solution explaining Euler's method of primality testing for Mersenne and Fermat numbers is given.