Possiamo usare diversamente i numeri di Wagstaff?

Numeri di Wagstaff e forma generalizzata

Wagstaff numbers and generalized form for Mersenne numbers (english version below)

I numeri di Wagstaff hanno delle potenzialità ancora inesplorate; la loro definizione è:

W = (2^p+1)/3 (1)

Nella (1) ci sono varie cose da evidenziare:

1) W è primo
2) 3 è primo
3) 1 è coprimo
4) p è primo

Generalizzando stiamo lavorando, quindi, con espressioni del tipo:

2^p1 + x = p2*d oppure 2^p1 = p2*d - x (2)

dove p1, p2 sono primi e d dispari

Nella (2) p2, rispetto alla (1), ha il ruolo del 3, d il ruolo di W e x il ruolo di 1.

Supponiamo al momento x=1 la (2) porta alla conclusione:

p1 = log2(p2*d-x) (3)

Quindi dalla (3) per un p1 assegnato (perchè ci è assegnato il numero di Mersenne 2^p1-1),

se è fissato p2 (il denominatore nella (1)) e se x = 1, allora facendo variare d si ottiene la uguaglianza (3).

In particolare è con x=1 il maggior numero di uguaglianze ottenibili avviene per p2=3.

Un'altro modo per sfruttare la (2) è, supponendo ancora x=1:

Mp=2^p1-1=p2*d-2 (4)

2^p1-1+2=p2*d (5)

Mp+2 = p2*d

La (5) dice che Mp+2 è un composto ottenuto dal prodotto di 2 numeri di cui almeno uno primo (grazie ai numeri di Wagstaff sappiamo che preferibilmente p2=3).

Teorema A:
Condizione necessaria e sufficiente affinchè Mp=2^p-1 sia primo è che siano vere tutte le tre condizioni:
1) p sia primo e di forma qualsiasi (4k+1 o 4k+3)
2) Se p=4k+3 deve essere S=2p+1 non primo
3) Mp+2 = 3*d con d numero primo

Es: 2^3-1=7 primo di Mersenne

allora la 1) è rispettata, la 2) anche; per la 3) è: 7+2=3*3 per cui Mp è primo

2^5-1+2=33=3*11

2^7-1+2=129=3*43

Qui 3, 11 e 43 sono proprio i numeri di Wagstaff.

Studio della forma 2^p1 = p2*d - x
Interessante è vedere il caso x diverso da 1, per cui la (2) diventa:
Mp= 2^p1 -1 = p2*d - x - 1 (6)

equivalente a:
Mp+x+1= p2*d

Vedremo che servono anche due condizioni:
x+1 = p1-1
p2 = p1

ovvero
Mp+p1-1 = p1*d (7) oppure
Mp = p1*d - (p1-1)
Mp=p1*d-phi(p1)

Con la generalizzazione (7) nasce il

Teorema B:
Condizione necessaria affinchè Mp=2^p1-1 sia primo è che siano vere tutte le tre le condizioni:
1) p1 sia primo e di forma qualsiasi (4k+1 o 4k+3)
2) Se p1=4k+3 deve essere S=2p1+1 non primo
3) Mp+p1-1 = p1*d con d dispari

le condizioni però da sole non sono sufficienti.

Adesso vedremo perché è vera la (7). Se nella (6) poniamo ad esempio:
x = 3
Mp + 4 = p2*d

esaminiamo ad esempio 2^3-1=7 primo di Mersenne, allora:

7+4=11 impossibile perchè 11 è primo e non si può scomporre come prodotto;quindi x+1=4 non va bene, mentre:

7+2=3*3 quindi 2^ 7-1 è primo.

Da notare che in 3*3 c'è proprio l'esponente p1=3 di Mp=2^3-1

Esempi
2^5-1=31
31 + 4 = 35=5*7=35 allora 31 è un numero primo di Mersenne!
Da notare che in 5*7 c'è proprio l'esponente p1=5 di Mp=2^5-1

2^7-1=127
127 + 6 = 133 = 7*19

2^13-1 + 12 = 8191+12=8203 = 13*631

Quindi
x+1 = p1-1

Primalità? Solo col Teorema A.
La (6), senza la generalizzazione ha anche un altro interesse, ovvero di primalità; ma vedremo che non è sufficiente.

Se d si sceglie come numero grande si potrebbe testare la primalità di un primo più piccolo, solo che le condizioni precedenti sono solo necessarie ma non sufficienti:

(Mp+p1-1)/d = p1 (8) oppure

(Mp+phi(p1))/d = p1 (9)

Ad esempio:

2^13-1 + 12 = (8191 + 12)/631 = 13 d=631 e dMp+p1-1

Si tratta quindi di trovare un divisore tale che sia vera la (8).

Ma non è detto che Mp sia primo; difatti:

2^37-1+36/3714566311 = 37 ma 2^37-1 non è primo.

In realtà le condizioni di prima come nella tecnica cinese servono solo a qualificare l'esponente di Mp come primo.Col Teorema A, invece, abbiamo anche la condizione di sufficienza e, quindi, la primalità.

English version

Wagstaff numbers have the potential still unexplored, and their definition is:

W = (2 ^ p +1) / 3 (1)

In (1) there are several things to highlight:

1) W is first
2) 3 is first
3) 1 is coprime
4) p is prime

Generalizing we are working, then, with expressions like:

2 ^ x = p1 + p2 * d ^ 2 or p1 = p2 * d - x (2)

where p1, p2 are prime numbers and d is odd.

In (2) p2, compared to (1), has the role of 3, p3, the role of the role of 1 W ex.

Suppose at x = 1 to (2) leads to these conclusions:

p1 = log2 (p2-d * x) (3)

Then from (3) for a given p1 (because there is assigned the Mersenne number 2 ^ p1-1),

if p2 is fixed (the denominator in (1)) and if x = 1, then by varying p3

we obtain the equality (3).

In particular, with x = 1 the largest number of equalities is obtained for p2 = 3

Another way to exploit the (2) is, if x = 1:
Mp = 2 ^ p1-1 = p2 * d-2 (4)
Mp +2 = p2 * d (5)

The (5) says that Mp +2 is a composite number (with Wagstaff we know that p2 = 3).

Theorem A (Rosario Turco):
Necessary and sufficient condition so that Mp = 2 ^ p-1 is a prime number is that all three conditions are true:
1) p is prime and of any shape (4k +1 or 4k +3)
2) If p = 4k +3 then S = 2p +1 mustn't be a prime number
3) Mp +2 = 3 * d with d prime number

Ex: 2 ^ 3-1 = 7 Mersenne prime

then 1) is true, the 2) also, for the 3) is: 7 +2 = 3 * 3 which Mp is prime

2 ^ p1 = p2 * d - x

form 2^p1 = p2*d - x
Interesting to see if x is not 1, so (2) becomes:

Mp = 2 ^ p1 -1 = p2 * d - x - 1 (6)

equivalent to:
Mp + x +1 = p2 * d

We will see that also serve two conditions:
x +1 = p1-1
p2 = p1

or
Mp+p1-1 = p1 * d (7) or
Mp=p1*d-(p1-1)
Mp=p1*d-phi(p1)

With the generalization (7) we have the

Theorem B (Rosario Turco):
Necessary condition so that Mp = 2 ^ (p1-1) is a prime number is that all three conditions:
1) p1 is a prime number and any shape (4k +1 or 4k +3)
2) If p1 = 4k +3 then S = 2p1 + 1 must be non-prime
3) Mp + p1-1 = p1 * d with d odd

but they aren't sufficient conditions.

Now we will see why (7) is true:

If in (6) say for example:

x = 3
Mp + 4 = p2 * p3

Ex: 2 ^ 3-1 = 7 Mersenne prime

7 +4 = 11 is prime. it is impossible 11=p1*p3, because x +1 = 4 is not good
7 +2 = 3 * 3 OK!! 2 ^ 7-1 is prime.

Note that in 3 * 3 is just the exponent p1 = 3 Mp = 2 ^ 3-1

Examples
2 ^ 5-1 = 31
31 + 4 = 35 = 5 * 7 = 35 then 31 is a Mersenne prime!
Note that in 5 * 7 is precisely the exponent p1 = 5 Mp = 2 ^ 5-1

2 ^ 7-1 = 127
127 + 6 = 133 = 7 * 19

2 ^ 13-1 + 12 = 8191 +12 = 8203 = 13 * 631

Hence:
x +1 = p1-1

Primality? Only with the Theorem A
The (6), without generalization has another interest (primality), but the previous conditions are only necessary.

If d is chosen as a big odd number (eg 127) you can check that

(Mp + p1-1) / d = p1 (8) or

(Mp+phi(p1))/d = p1 (9)

Eg

2 ^ 13-1 = (8191 + 12) / 631 = 13 and d is a divisor of Mp+p1-1. So I must search a divisor d of Mp+p1-1 such that the (8) is true.

Only Theorem A is useful for primality.