Explore BrainMass

Primality of Mersenne Numbers

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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

© BrainMass Inc. brainmass.com October 25, 2018, 12:40 am 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.

See Also This Related BrainMass Solution

Perfect and amicable numbers

1) See attached

2) Show that 28 is a perfect number.

3) What is the amicable number to 17296?

4) Express all 5/11 as the sum of distinct unit fractions.

5) Using modular arithmetic, derive a formula to find all numbers that meet the following conditions:
- Divide by 3 the remainder is 1
- Divide by 5 the remainder is 0

6) What is the area of a triangle with lengths of sides 28, 30 and 32?

7) What is the probability of picking 6 numbers out of 53 numbers and getting
4 out of 6 numbers correct?

8) Lagrange contributed a great deal to the metric system. How would you show your students how to use the metric highway below?

See attached

9) See attached

10) See attached

11) Chevalier de Mere's Problem-

How many times must you throw two die in order to have half a chance of getting double sixes? (The original problem used the word dice but die is singular and dice is plural i.e., a pair of dice is two die.)
We know that (see attached). If you roll dice you have 36 outcomes. Also the probability of getting at least one double 6 on n rolls of the dice is the same as getting no double sixes on n rolls of a dice.
The probability of double sixes is 1/36. The probability of any combination other than double sixes is 35/36.
Thus, Pascal and Fermat concluded that solving for n in the formula below will solve the problem.

See attached

What is the minimum number of rolls of the dice to have at least 1/2 chance of getting double sixes?

12) Explain how to multiply 88 times 112 using Egyptian multiplication.

13) What 3 expressions can generate all Pythagorean triples.

14) Find an arithmetical progression with 5 terms, sum 11, and common difference 1/2.

View Full Posting Details