Radice primitiva di un numero primo

Radice primitiva di un numero primo

Nei blog precedenti abbiamo visto che il Teorema B dimostrava solo la primalità dell'esponente; ma lo stesso procedimento può servire, invece, a risolvere altro.

Uno dei problemi fondamentali nella ricerca della primalità di un numero primo è che se quest'ultimo è molto grande occorre affidarsi a metodi probabilistici, che comunque richiedono tempo per dare un responso.

Il numero di Wagstaff dà l'illusione di ridurre il numero primo da valutare ad 1/3; però se si trasforma il numero che si ottiene in binario (binary di PARI/GP) il risparmio è di 1 bit che è poca cosa.

E' chiaro che se esistesse un metodo tale che per poter sapere se un numero enorme è primo sia sufficiente riferirsi ad un numero molto più basso, sarebbe a dir poco eccezionale. In teoria metodi del genere esistono, ma nella pratica si scontrano con le implementazioni e i limiti hardware e software.

Abbiamo visto col Piccolo Teorema di Fermat che se è dato un numero primo p, allora a^(p-1) mod p = 1 per tutti gli a nell'intervallo (1,p-1).

Si definisce radice primitiva di p qualsiasi numero r tale che per ogni a appartenente all'intervallo (1,p-1) è a=r^k mod p con k&gt 1. Se p è dispari allora r è una radice primitiva di p se e solo se r^(p-1/q) mod p > 1 per ogni q divisore primo di r, allora p è primo.

Più esattamente è sufficiente che siano vere due condizioni:
r^(p-1/q) mod p > 1
r^(p-1) mod p = 1

Radice primitive di un numero primo ne esistono minimo una o più di una.

Ad esempio se p=13 r=2 è una radice primitiva di p=13; per cui p è primo

Infatti:
p-1 = 12
i divisori primi di p-1 sono q=2,3 (non dobbiamo prendere le potenze)

Scelgo 2 inizialmente e per ogni ottengo:
2^(12/2) mod 12 = 4 > 1
2^(12/3) mod 12 = 4 > 1

2^(12) mod 13 = 1

per cui già r=2 è buono.

Dovè il difetto di tutto questo? Supponiamo che il numero primo da verificare è un numero di Mersenne Mp=2^p-1 con p alto; allora le due condizioni diventano nel caso del numero di Mersenne di cercare un
r tale che:
r^((2^p-2)/q) mod p > 1
r^(2^p-2) mod p = 1

Ma abbiamo a che fare ora con una potenza di una potenza ... a parte il fatto che spesso è intrattabile lo stesso 2^p-2; in ogni caso si ricade nella ricerca di divisori q.

Uhmm ...

Costanti legate ai numeri di Mersenne

Costanti legate ai numeri di Mersenne

Come curiosità riporto la costante di Erdos-Borwein EB: è la somma dei reciproci dei numeri di Mersenne. EB dal nome di Paul Erdos e da Peter Borwein.

EB = sum(n=1,inf,  1/(2^n-1) ) = 1,606695152415291763...
dove inf qui rappresenta infinito: è una serie.

In realtà se facciamo una prova si scopre che tale valore di costante è raggiunto già con 100 termini. Ad esempio ciò si vede con un semplice programma PARI/GP del tipo:

St0(end) = local(A=0.0); {
  A = sum(x=1,end, 1./(2^x-1));
  printp("A = ", A);
}

Che succede se studiamo una analoga espressione ma con gli inversi dei numeri primi di Mersenne (CT1), dei quadrati degli inversi dei numeri primi di Mersenne (CT2), dei cubi (CT3) e delle potenze quinte (CT5)?

Nascono altre costanti:
CT1 = 0.5164541789407885653304873430...
CT2 = 0.1326218721933906054374640689
CT3 = 0.03998654430857385092742336216...
CT5 = 0.004174760315415187189620198382...

ognuna varia lentissimamente le ultime cifre ma solo quando si trova un numero primo di Mersenne.
Anche qua per raggiungere questi valori sono sufficienti 100 termini ed un programmino come il seguente:

St(end, exp=1) = local(x=1, A=0.0); {
  forprime(x=2, end,
     if( isprime(2^x-1) == 1,
         A = A+1./((2^x-1))^exp;
         printp("x = ",x, " A = ", A);
     ); 
  );
}

English version

Constants related to the Mersenne numbers

As a curiosity I show the Erdos-Borwein constant EB: it is the sum of the reciprocals of the Mersenne numbers. EB by the name of Paul Erdos and Peter Borwein:

EB = sum (n = 1, inf, 1 / (2 ^ n-1)) = 1.606695152415291763 ...
where inf is infinity here is a series.

In fact, if we try we discover that this constant value is reached already with 100 terms. For example, this is seen with a simple program PARI / GP type:

St0 (end) = local (A = 0.0), (
   A = sum (x = 1, end, 1. / (2 ^ x-1));
   printp( "A =", A);
)

What if we study a similar expression but with the inverse of Mersenne primes (CT1), the squares of the inverse of Mersenne primes (CT2), cubes (CT3) and fifth powers (CT5)?

Born other constants:

CT1 = 0.5164541789407885653304873430 ...
CT2 = 0.1326218721933906054374640689...
CT3 = 0.03998654430857385092742336216 ...
CT5 = 0.004174760315415187189620198382 ...

each constant varies very slowly to the latest figures but only when there is a Mersenne prime.
Even here for these values are sufficient to reach 100 prime numbers and a program like this:

St (end, exp = 1) = local (x = 1, A = 0.0), (
   forprime (x = 2, end,
      if (isprime (2 ^ x-1) == 1,
          A = A +1. / ((2 ^ x-1)) ^ exp;
          printp( "x =", x, "A =", A);
      ) ;
   ) ;
)

Teorema B : (Mp+p1-1)/d = p1

Teorema B : (Mp+p-1)/d = p

Come visto nel blog precedente, il Teorema B dà solo condizioni necessarie e non è efficace per la primalità di Mp, ma solo di p. Possiamo dimostrare questo? si.

Il Piccolo Teorema di Fermat afferma che se p è primo allora deve poter dividere 2^(p-1)-1. Siamo in queste condizioni? Vediamo.

Mp + p - 1 = p*d (1)

2^p - 1 + p -1 = p *d

2^p = p*d -p + 2

moltiplichiamo e dividiamo per 2 entrambi i membri:
2/2 * 2^p = 2/2(p*d-p) + 2/2*2

2* 2^(p-1) = 2/2(p*d-p) + 2/2*2

sposto a sinistra il termine 2/2*2 = 2

2*(2^(p-1)-1) = p*d - p

divido per p e per 2

(2^(p-1)-1)/p = (d-1)/2 (2)

Ovvero siamo nella condizioni del Piccolo Teorema di Fermat.

Facciamo un esempio:

2^37-1 con tale tecnica riusciamo a dire solo che 37 è primo; infatti:

2^36-1/37 = 1857283155
n= (2^(p-1)+p-1)/p=3714566311
(n-1)/2 = 1857283155

La (2), che ingloba il significato del Piccolo Teorema di Fermat, è ricavata dalla (1); per cui il Teorema B ci porta solo a dire che l'esponente di Mp è primo.

Perchè il Teorema A è vero
Abbiamo visto nel blog precedente che Mp + 2 = p2*p3 in generale con Mp = 2^p1-1

Il che è equivalente al fatto che:

(2^p1+1)/p2 =p3

Ora 2^p1+1 è primo se p1=2k; poichè p1 lo stiamo ipotizzando numero primo allora 2^p1+1 è composto; Es: 2^3+1=9 2^5+1=33 2^7+1=129 etc

Per essere composto può essere:
p1=4k+1 con k pari ma potenza dispari di 2 (k=2^1, k=2^3 etc)
es: 4*2+1=9, 4*2^3+1=33
p1=4k+3 con k>1 e dispari e multiplo di 3 (k=3,6,9etc)

Da quello di sopra si vede che un divisore p2 di 2^p1+1 è proprio p2=3; difatti ogni
(2^p1+1)%9 = 3 oppure 6 se p1>3.

Se p2=3, allora p3 è un primo? Sì, perchè è vero anche che:

(2^p1+1)/p3 = p2

English version

Theorem B: (mp + p-1) / d = p

As seen in previous blog Theorem B gives only necessary conditions, and is not effective for the primality of Mp, but only by p. We can prove this? yes.

The Fermat's little theorem states that if p is prime then must divide 2 ^ (p-1) -1. We are in these conditions? Let's see.

Mp + p - 1 = p * d (1)
2 ^ p - 1 + p -1 = p * d
2 ^ p = p * d-p + 2

I multiply and divide by 2 both sides: 2 / 2 * 2 ^ p = 2 / 2 (p * d-p) + 2 / 2 * 2
2 * 2 ^ (p-1) = 2 / 2 (p * d-p) + 2 / 2 * 2

I move left the term 2 / 2 * 2 = 2
2 * (2 ^ (p-1) -1) = p*d - p

I divided by p and 2
(2 ^ (p-1) -1) / p = (d-1) / 2 (2)

Now we are in terms of Fermat's little theorem.

For example:
2 ^ 37-1 with this technique we can only say that 37 is prime, because:
2 ^ 36-1/37 = 1857283155
n = (2 ^ (p-1) + p-1) / p = 3714566311
(n-1) / 2 = 1857283155

The (2), which incorporates the significance of Fermat's little theorem, is obtained from (1) and hence Theorem B leads only to say that the exponent of Mp is prime.

Why Theorem A is true?
We saw in the previous blog that Mp + 2 = p2 * p3 in general with Mp = 2 ^ p1-1

Which is equivalent to the fact that:

(2 ^ p1 +1) / p2 = p3

Now 2 ^ p1 +1 is a prime number if p1 = 2k; but if p1 is a prime number then 2 ^ p1 +1 is composite. Ex: 2 ^ 3 +1 = 9 2 ^ 5 +1 = 33 2 ^ 7 +1 = 129 etc

So it must be:
p1=4k+1 with k even but odd power of 2 (k=2^1, k=2^3 etc)
es: 4*2+1=9, 4*2^3+1=33
p1=4k+3 with k>1 and odd, multiple of 3 (k=3,6,9 etc)

So a divisor of 2 ^ p1 +1 is p2 = 3; infact each (2 ^ p1 +1)% 9 = 3 or 6 if p1>3.

If p2 = 3, p3 is a prime number? Yes, because it is also true that

(2 ^ p1 +1) / p3 = p2.

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.

Primalità con i Numeri perfetti

Test di primalità attraverso i numeri perfetti

Affrontiamo il tema delle cifre finali di Np. Sappiamo che:

Np = 2^(n-1) * (2^n-1) = A * B

Ora è evidente che n deve essere primo (dispari) e n-1 pari perchè legati da Np.

In generale se si fa la prova del 9 di un prodotto:
- si determina il modulo 9 dei due fattori
- si moltiplicano i risultati modulo ottenuti
- si fa il modulo 9 del risultato finale

Per cui è:
Np mod 9 = ( 2^(n-1) mod 9 * (2^n-1) mod 9 ) mod 9

Anche qui si possono osservare cicli esanumerici per ogni fattore e le RN (radici numeriche) di A e B.

Sono eliminati dal ciclo le situazioni per cui B non è primo (es: 2^11-1 n.p.).

CICLI ESANUMERICI DI NP (OGNI 6)

A=2^(n-1)..B=(2^n - 1).........A*B......RN A...RN B
---------------------------------------------------------------
2^2=4.......(2^3 - 1)=7.........28.......4.........7
2^4=16.....(2^5 - 1)=31........496......7.........4
2^6=64.....(2^7 - 1)=127.......8128.....1.........1
---------------------------------------------------------------
2^8=256...(2^9 - 1)=511......130816.......4.........7
2^10......(2^11 -1)...............n.p.........7.........4
2^12=4096.(2^13 - 1)=8191....33550336...1.........1
---------------------------------------------------------------
n.p. significa non primo.

Nei due cicli esanumerici si osservano le seguenti cose:
1) l'alternanza accoppiata delle due sequenza RN A e RN B: 4.7.1/7.4.1 all'infinito
perchè A e B sono legati dalla formula di Np escludendo i numeri Mersenne non primi
2) Np=A*B termina per:
- 28 preceduto da dispari quando A termina con 4 preceduto da pari
- 6 preceduto da dispari quando A termina per 6 preceduto da dispari
3) il prodotto (RN A * RN B) mod 9 a causa dell'alternanza 4.7.1/7.4.1 dà sempre 1

Test di primalità dei numeri primi di Mersenne co i numeri perfetti?


E' possibile creare un test di primalità dei numeri di Mersenne basato quindi sulriconoscimento dei numeri perfetti Np? Attualmente non è dimostrato che si possa fare o per lo meno è come se mancasse qualche altra condizione.

Ad esempio: dato un esponente p tale che si debba valutare se 2^p-1 è primo, allora se p è primo, e sono esclusi i casi per cui p=4k+3 tale che S=2*p+1 è primo, se( 2^(p-1) mod 9 * (2^p-1) mod 9 ) mod 9 = 1 e Np=2^(p-1) * (2^p-1) terminacon 6 preceduto da dispari o con 28 preceduto da dispari, allora 2^p-1 è primo.

Sembra tutto perfetto! Provatelo con numeri primi di Mersenne piuttosto grandi e vi renderete conto che non sempre funziona: va bene per valori bassi.


Alla prossima

Doppi numeri perfetti

Doppi Numeri perfetti (Double Perfect Number)

Se indichiamo con Np un numero perfetto, esistono i doppi numeri perfetti NNp? Sì.

Sappiamo che esistono i numeri primi di Mersenne e i doppi numeri di Mersenne:

Mp = 2^p-1
MMp = 2^Mp -1

da cui:
Np = 2^(p-1)*Mp
NNp = 2^(Mp-1)*MMp

Esempio:
M2 = 2^2-1=3
MM2 = 2^M2-1 = 2^3-1=7

N2 = 2*3=6=2^1*(2^2-1)=2*M2
NN2 = 2^(M2-1) * MM2 = 2^2*7=28 numero perfetto.

Altro problema: perchè i numeri perfetti terminano per 6 preceduto da un dispari oppure con 28 preceduto da un dispari? Aspetto vostre proposte.

Forme particolari

Proviamo a studiare l'espessione:
S=2^n*p + sum(i=0,n-1,2^i) (1)

La (1) è una forma particolare che fa parte della forma generale dei numeri di Hailstone
n1=2^n2+c, dove la sommatoria corrisponde ai "numeri bizzarri di Collatz".

Proprietà della (1)
Se n=1, p è primo con p=4k+3 e S=2p+1 è primo, allora Mp=2^p-1 è composto.

I numeri bizzarri di Collatz sono del tipo (2^k-4)/4. Condizione necessaria ma non sufficiente affinchè un numero bizzarro di Collatz sia un numero primo di Mersenne è che k-2 sia primo.
Difatti 2^k/4 -1 = 2^(k-2) - 1

Se n è dispari maggiore di 1 e p=4k+3 con S primo nella (1), allora come è Mp? Aspetto qualche vostra buona proposta.

Nella (1) la parte 2^n*p è sempre pari.

La formula (1) non trova tutti i numeri primi di Mersenne.

In (1) se n è pari e potenza di 2 allora S e p (ma con p diverso da 2) terminano con la stessa cifra.

Se n è dispari, p è primo e la somma ripetuta delle cifre di (2^n*p) mod9=1 allora il numero 2^n*p è un numero perfetto.

Dalla (1) è possibile avere situazioni in cui A=2^n*p sia un numero perfetto (es: 2^2*7=28 n=2) con B=sum(i=0,n-1,2^i) numero primo di Mersenne (es: n=2 sum=2^0+2^1=3=2^2-1) e S=A+B va valutato se numero primo (in alcuni casi lo è; es: 28+3=31).

Numeri perfetti

Numeri perfetti

Definizione
Un numero perfetto è un numero uguale alla somma dei suoi divisori (escluso sè stesso).

Es: 28
I divisori di 28 sono 1,2,4,7,14,28. Se escludiamo 28 come da definizione allora la somma dei termini rimasti dà 28.

Eulero
Un numero Np perfetto è tale che Np=2^(p-1)*(2^p-1)

Qualche esempio sul perchè della formula. Consideriamo la somma: 1+2+4=7

1+2+4 = 7 è la somma delle potenze di 2 con esponente i=0,...,2 ed equivale in PARI a sum(i=0,2,2^i). 7 è un numero primo, ed è anche un numero primo di Mersenne 7=2^3-1.

Prendiamo il 4 è l'ultimo termine della sommatoria ovvero 2^2. Se faccio Np = 4*7=28
Np è un numero perfetto.

Un numero perfetto quindi è tale che:

Np = (somma) * (ultimo termine della somma)

dove:
somma = 7
ultimo termine della somma = 4

Che legame esista tra 4 e 7? 4 = 2^2 =2^(3-1) e 7=2^3-1 per cui da qui nasce la formula di Eulero.

Proposizione: I numeri perfetti sono ottenibili da forme del tipo 2^n*p, con p primo di Mersenne ed n pari con n=p-1.

Fermat
Radicali dei numeri perfetti

E R
1 1
2 3
3 7
4 15
5 31
6 63
7 127
8 255
9 511
10 1023
11 2047
12 4095
13 8191

Se la prima colonna E è l'insieme dei numeri naturali, che chiamiamo "esponenti" E, e la seconda
colonna è quella dei numeri più piccoli di un'unità in una progressione di passo 2, che chiamiamo "radicali del numero perfetto" R, allora:

- se l'esponente è composto anche il radicale del numero perfetto è composto.
- se l'esponente è primo, il suo radicale - 1 è divisibile per il doppio dell'esponente

es: 7 primo, esponente di 127, allora 126 è divisibile per 2*7=14

- se l'esponente è primo, allora il radicale non è divisibile per nessun primo, tranne
quelli maggiori di 1 dei multipli del doppio dell'esponente.

Un numero triangolare è dato dalla somma dei numeri consecutivi a partire da 1.
Es: 3=1+2, 6=1+2+3, 10=1+2+3+4

Un numero esagonale è dato dalla forma n(2*n-1). Sono anche triangolari alternati, formati
da un numero dispari di addendi.

Radice numerica di N
Si dice radice numerica di N la somma ripetuta delle sue cifre fino a rimanere con una sola cifra.
E' equivalente a N mod 9.

Nicomaco di Gerasa
I numeri perfetti pari terminano in 6 o in 28, preceduto da un dispari.
Ogni numero perfetto è triangolare.
Ogni numero perfetto è esagonale.

Teorema di Filippo Giordano
Ogni numero perfetto, escluso il 6, ha radice numerica 1.

Perchè 6 è escluso?

CICLI ESANUMERICI (ogni 6)
2^(n-1)*(2^n - 1) prodotto Radice numerica
---------------------------------------------
2^(1-1)*(2^1 - 1) 1 1
2^(2-1)*(2^2 - 1) 6 6
2^(3-1)*(2^3 - 1) 28 1
2^(4-1)*(2^4 - 1) 120 3
2^(5-1)*(2^5 - 1) 496 1
2^(6-1)*(2^6 - 1) 2016 9
---------------------------------------------
2^(7-1)*(2^7 - 1) 8128 1
2^(8-1)*(2^8 - 1) 32640 6
2^(9-1)*(2^9 - 1) 130816 1
2^(10-1)*(2^10 - 1) 523776 3
2^(11-1)*(2^11 - 1) 2096128 1
2^(12-1)*(2^12 - 1) 8386560 9
------------------------------------------
... ...

Sopra sono riportati due cicli esanumerici, dove è evidente una ripetizione all'infinito
della radice numerica 1.6.1.3.1.9

I primi due cicli esanumerici dell'esempio presentano almeno 4 numeri perfetti corrispondenti
a n=2,3,5,7

I numeri con n dispari hanno radice numerica 1, mentre quelli con n pari hanno
alternativamente radice numerica 3 o multiplo di 3 (6-3-9).

Il 6 è un numero perfetto ottenuto da 2^(2-1)*(2^2-1)=2*3=6 quindi ottenuto con
esponente n = 2.

Poichè condizione necessaria affinchè 2^n -1 sia un numero primo è che n sia primo, e solo con i
numeri n dispari si ha radice numerica 1, allora n=2 è escluso e di conseguenza 6 non rientra nel
Teorema di Filippo Giordano.

Somma dei reciproci dei divisori di un numero perfetto
La somma dei reciproci dei divisori di un numero perfetto, incluso il numero perfetto, è 2.

Es:
6+6=1+2+3+6
Se dividiamo per 6 esce:

2 = 1/6 + 2/6 + 3/6 + 6/6 = 1 + 1/2 + 1/3 + 1/6

per 28:

2 = 1/1 + 1/2 + 1/4 + 1/7 + 1/14 + 1/28

Somma di una successione di dispari consecutivi al cubo
Un 'altra particolarità dei numeri perfetti è che si possono ottenere dalla somma di una successione di dispari consecutivi al cubo.

Esempio:
28 = 1^3 + 3^3
496=1^3+3^3+5^3+7^3
8128=1^3+3^3+5^3+7^3+9^3+11^3+13^3+15^3

Numero binario di un numero perfetto

Ecco alcuni numeri di Mersenne primi in binario

110, 11100 , 111110000,1111111000000

Si nota che: "un numero perfetto in binario è caratterizzato da un numero k dispari di "1" e un numero m=k-1 pari
di zeri"

Alla prossima

Numeri di Mersenne composti

Numeri di Mersenne composti

Abbiamo visto che una delle tecniche di primalità possibili da usare è anche la ricerca di piccoli fattori; in altri termini si tenta di fattorizzare il numero di Mersenne.

Un teorema su cui basarsi potrebbe essere:
Let p and q be primes. If q divides Mp = 2^p-1, then
q = +/-1 (mod 8) and q = 2kp + 1 for some integer k.

Mp=2^11-1
q= 2*11+1=23
Mp/q= 89
Mp isn't a Mersenne's prime!

E' ovviamente usabile anche per i "double Mersenne's prime" MMp.
So
Let Mp and q be primes. If q divides MMp = 2^Mp-1, then
q = +/-1 (mod 8) and q = 2kMp + 1 for some integer k.

Un algoritmo semplice in PARI/GP potrebbe essere:

TestM(p) = local(status=1, k=1, q=1, Mp=1);{
print(" ");
print("********");
print("Test Mp");
print("********");
print(" ");

printp("p = \t", p);

/* Mp=2^p-1; This explode!! */

Mp=shift(Mp,p);
Mp = Mp - 1;
printp("Mp = \t", Mp);

while( status == 1 & k < Mp & q < Mp,
k=k+1;
q=(2*k)*p + 1;
if( isprime(q) == 1 & q < Mp,
if(lift(Mod(q,8)) == 7 | lift(Mod(q,8)) == 1,
if( lift(Mod(Mp,q)) == 0, status=0; printp("q = \t", q);
printp("Mod = \t", lift(Mod(Mp,q)););
printp("k = \t", k);
printp("Not Prime!");
q=Mp; k=Mp;
/* I stop at the first small factor */
);
);
);
);
if( status == 1, printp("Prime!"););
return(status);
}

Un altro metodo interessante che evita di combattere con l'esplosione della potenza è il seguente.

Il DNA del numero di Mersenne è nell'esponente; per cui si cerca di trovare il piccolo fattore nell'esponente: esiste un algoritmo efficiente per determinare se un numero divide 2^p-1. Per esempio se vogliamo vedere se abbiamo a che fare con S=2p+1 (numeri di Sophie Germain) con p=4k+3 (per puntualizzare), tale che Mp non è un numero primo, allora se abbiamo 2^23-1 occorre vedere se 47 divide 2^23-1. Si converte l'esponente 23 in binario 10111 e si parte dalla prima cifra a sinistra. Rimuoviamo, si dice, il top bit dall'esponente ne valutiamo il quadrato e lo moltiplichiamo per 2 poi valutiamo il resto di esso (modulo 47 nell'esempio) come nello schema di sotto.

Square -------- Top bit ----- Mult by 2 ------- Mod N
1*1 = 1 -------- 1 0111 ----- 1*2 = 2 ------------- 2
2*2 = 4 --------0 111 ----- ----no --------------- 4
4*4 = 16 ---------1 11 ------- 16*2 = 32 ---------- 32
32*32 = 1024 ----1 1 --------1024*2 = 2048------ 27
27*27 = 729 ------1 ----------729*2 = 1458 -------1

Alla fine si ottiene in basso a destra 1, ovvero significa che: 2^23 = 1 mod 47 (1) e questo evitando le potenze. Se sottraiamo 1 da entrambi i membri della (1) si ottiene che: 2^23-1 = 0 mod 47. Questo dimostra che 2^23-1 è un composto.

Un'altra tecnica è data dal Teorema:"Se p e q sono primi, se q divide Mp=2^p-1 allora q=+/- 1 mod 8 e q=2kp+1 per qualche k". E' equivalente a dire che "Se p è primo e per qualche k q=+/- 1 mod 8 e q=2kp+1, allora Mp è composto. Tale tecnica è sfruttabile per trovare un fattore del numero di Mersenn

Un algoritmo didattico a tal proposito in PARI/GP è presentato di seguito.
Se dobbiamo testare 2^23-1 dobbiamo passare solo l'esponente 23. Es: TM(23).

TM(p) = local(status=1, i=1, len=0, S=0);{

print(" ");
print("********");
print("Test 2p+1");
print("********");
print(" ");

printp("p = \t", p);
S=2*p+1;
printp("S = \t", S);

len = length(binary(p));
B = Vecsmall(binary(p));

printp(B);
printp("len = ", len);

q = B[i]*B[i];
printp("Square = ", q);

while( i<=len & status ==1,
printp("Top bit ", B[i]);
if( B[i] != 0,
q = q*2;
printp("Mul by 2 = ", q);
);

r = q%S;
printp("Mod = ", r);
q = r*r;
printp("Square = ", q);

if( i == len & r == 1,
status = 0;
printp("Not Prime!");
);
i++;
);

return(status);
}