0

The following example shows a primetest for Mersenne numbers.

It's based on two theorems:

1) The largest prime devider of a number n is $\lfloor\sqrt{n} \rfloor$.

2) Divisor of $M_{17}$ for example are of the form $2*17k+1$.

Example:

enter image description here

Why do we only have to check the divisors of the form $2*13k+1$ less than $\lfloor\sqrt{n}\rfloor$ that are prime?

WinstonCherf
  • 1,022
  • What about the explanation in the image do you not understand? – Mees de Vries Dec 13 '17 at 13:45
  • Why do we only have to check the divisors of the form 2∗13k+1 less than ⌊√n⌋ that are prime? Why do we not have to check the divisor 2131+1=27 (which is not prime) for example? – WinstonCherf Dec 13 '17 at 13:49
  • 1
    If a number $n$ is non-prime it must have a prime divisor less than $\sqrt{n}$, thus it suffices to look for prime divisors less than $\sqrt{n}$ to prove that $n$ is non-prime. Then the theorem tells us that such prime divisors can only take a limited number of forms. Sure, you can check non-prime numbers of the form $2 \times 13k + 1$, but if those divide $M_{13}$, then that non-prime must have a prime divisor which is also of that form, so there is no reason. – Mees de Vries Dec 13 '17 at 13:54

1 Answers1

0

Interesting question, Lene. As I understand, you're asking why (2^p - 1) can only have prime factors of the form (2pk+1). Consider the following informal proof:

Construct a table, with the zeroeth column consisting of all the primes, the first column consisting of the smallest Mersenne numbers which are multiples of that prime, and each row thereafter consisting of all the Mersenne numbers which are multiples of that prime. It looks something like this:

0___1_____2_____ 3___

3, (2^2-1), (2^4-1), (2^6-1)...

5, (2^4-1), (2^8-1), (2^12-1)...

7, (2^3-1), (2^6-1), (2^9-1)...

11, (2^10-1), (2^20-1), (2^30-1)...

Note several facts about this table:

(1) If the first exponent of the row is $x$, subsequent exponents will be 2$x$, 3$x$, 4$x$ etc. This is the case, because if ((2^$x$)-1) is a multiple of p, then (2^(2$x$)-2^$x$) is also a multiple of p. Add (2^$x$-1) to this, and we get (2^(2$x$)-1), a multiple of p.

(2) All Mersenne numbers appear somewhere in this table, at least once (as it must either have multiple prime factors, or be a prime itself)

(3) A Mersenne number with a prime exponent can appear only once in the table, and in the first column.

(4) For any prime $p$, the Mersenne number (2^($p$-1)-1) must appear in its row (Fermat's little theorem).

(5) If (2^($p$-1)-1) is to appear in the first column of any row, it will appear in a row with a prime of the form kp+1.

Thus, (2^p-1) can only have prime factors of the form (2pk+1).

Thomas Delaney
  • 1,683