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
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 ...
A detailed solution explaining Euler's method of primality testing for Mersenne and Fermat numbers is given.