Nella teoria dei numeri è denominato "numero primo di Sophie Germain" quel numero primo q tale che anche p = 2q + 1 è primo.  A sua volta ogni primo della forma  p = 2q + 1 , con q primo, si dice "primo sicuro".

In questa pagina daremo una risposta alla seguente domanda:

“ In che modo si può stabilire se un numero intero della forma p = 2q+1 è primo o multiplo? ”

Per testare questa categoria di numeri primi, nel caso particolare in cui q sia primo, viene in nostro aiuto uno dei corollari del teorema principale  VTL - (Wn) _b  con una condizione necessaria e sufficiente. 

Eccone l'enunciato, ma si tenga presente che i polinomi vanno considerati solo per il loro valore numerico.

                                           Teorema VTL - W_b(2p)           * (vedi nota)

Sia q primo  e  p = 2q+1

Condizione necessaria e sufficiente affinché p sia primo è che p divida ( b ^q +1 ) oppure ( b ^q  - 1 ).

Ricorrendo alle congruenze, l'enunciato avrà la forma :

b ^q ≡ ± 1  (mod. p)   Û    p è primo

essendo b un qualsiasi numero intero coprimo con p.   

Poiché il teorema vale per una base qualsiasi, è preferibile porre b = 2.

Cosicché, se p è primo, p deve dividere uno solo dei due numeri: ( 2 ^q + 1 ) ; ( 2 ^q - 1 )

Viceversa, se p divide uno solo dei due numeri, p è primo.

 

Facciamo degli esempi di come applicare il teorema VTL-W_b(2p) considerando numeri di poche cifre, per rendere più semplice la trattazione.  Eseguiremo i calcoli con l’uso della calcolatrice a 32 cifre di windows .

wtw     Stabiliamo se 59 è numero primo.

Poiché  59 = 2 ● 29 + 1 , e  29  è  primo, possiamo ricorrere al teorema VTL - W_b(2p)  per avere una risposta certa.

   Eseguiamo i calcoli per b = 10:                                  10²⁹ +1 = 59 ● 1694915254237288135593220339

   Ma  per b = 2  i calcoli sono più semplici:                  2²⁹ +1 = 59 ● 1909950

   Per b = 5 , si ha quest'altra uguaglianza:                      5²⁹ -1 = 59 ● 3157025676662639036

Da ciascuna di queste tre uguaglianze ne segue, senza alcun dubbio, che 59 è numero primo.                     

wtw     Dato il numero primo q = 659,  sia p = 2 ● 659 + 1 = 1319

Stabiliamo se 1319 è primo o multiplo usando il teorema VTL -W_b(2p).

In questo caso, per eseguire la divisione richiesta dal teorema, avendo a disposizione la calcolatrice di Windows a sole 32 cifre, è necessario ricorrere alle congruenze.

 2 ⁶⁵⁹ ≡ x  (mod. 1319) 

2 ⁶⁵⁹  = 2 ● 2 ^{2 * 7 * 47} ≡ 2 ● 809 ^{2 * 7} ≡ 2 ● 392 ² ≡ 1   (mod. 1319)  

Il risultato di questi calcoli ci fa dedurre che 1319 è certamente numero primo.

wtw     Dato il numero primo q = 7109,  sia  p = 2 ● 7109 + 1 = 14219

Stabiliamo se 14219 è primo o multiplo usando il teorema VTL -W_b(2p).

Ricorriamo alla congruenza:

 2 ⁷¹⁰⁹  ≡ x   (mod. 14219)

2 ⁷¹⁰⁹  = 2 ⁹ ● 2 ^{71 * 100} ≡ 2 ⁹ ● 8210 ⁷¹ ≡ 2 ⁹ ● 8210 ● 8210 ^7*10 ≡  2 ⁹ ● 8210 ●16 ¹⁰ ≡  3406  ( mod. 14219)

Il risultato di questi calcoli ci fa dedurre che 14219 certamente non è numero primo.   Infatti:  14219 = 59 ● 241

wtw     Stabiliamo se il numero  p = 2047 è primo.  

            Posto  2047 = 2 ● 1023 + 1, verifichiamo le uguaglianze:  (2 ¹⁰²³ + 1) = m ● 2047   ;   (2¹⁰²³-1) = m ● 2047 ,  senza sapere se 1023 sia

            primo o composto. 

            Dato che   2047 | (2¹⁰²³-1)  e  2047 ∤ (2 ¹⁰²³ + 1) ,  per il teorema VTL - W_b(2p) , nel caso in cui 1023  fosse primo,  anche 2047

            sarebbe primo.

            Cambiamo la base e ripetiamo i calcoli:

            2047 ∤ (3¹⁰²³-1)  e  2047 ∤ (2 ¹⁰²³ + 1) ,  quindi  2047 è numero composto e di conseguenza anche 1023 è composto!  

wtw     Stabiliamo se il numero  p = 1511 è primo.   

             Posto 1511 = 2 ● 755 + 1 , si ha: 1511| (2⁷⁵⁵-1) , ma  l'esponente 755 è  palesemente numero composto, quindi non possiamo essere

             sicuri che 1511 sia primo.

             Cambiando la base e rifacendo i calcoli ci rendiamo conto che, nel caso in cui 1511 fosse primo, la prova sarebbe sempre positiva,

             ma senza darci mai la certezza della sua primalità.

Ci chiediamo quindi se sia possibile accertarci che 1511 sia sicuramente primo o sicuramente multiplo.

La risposta certa ce la dà il teorema VTL - (W1510)_b                             

Sia dato il polinomio ciclotomico di ordine 1510, che scriviamo nella forma semplificata:

F₁₅₁₀(x) = [(b^{a c} + 1) (b + 1)] / [(b^a + 1)(b ^c + 1)]

Da questa formula si deduce che, affinché sia primo, 1511 deve dividere  (b + 1)(b ⁷⁵⁵ + 1), ma non deve dividere né (b¹⁵¹  + 1) né (b ⁵ + 1).

Procediamo con le prove.

Per  x = 2   si ha:  1511 ∤ W₂(1510)   

Altrettanto accade per x = 3, 4, 5, 6, 7, 8, 9, 10 .

Per x = 11  invece si ha:  1511|(11⁷⁵⁵ + 1) ● 12   ;   1511 ∤ (11¹⁵¹ + 1)   ;   1511 ∤ (11⁵ +1)

Cosicché possiamo concludere con la certezza che 1511 è primo.

wtw     Dato il numero primo 83 = 2 ● 41 + 1 , verifichiamo se divide i binomi:  (2⁴¹-1)   e   (2⁴¹+1)

             Dato che 83 è primo e anche 41 è primo,  il teorema VTL - W(2p) ci assicura la divisibilità di uno solo dei due binomi per 83:

                                      2⁴¹ + 1 = 83 ● 26494256091  ;    83 ∤ (2⁴¹ - 1) 

wtw     Dato il numero primo 61 = 2 ● 30 + 1 , verifichiamo se 61 divide i binomi (2³⁰-1)  e (2³⁰+1)

             Dato che 61 è primo, ma 30 non è primo,  il teorema VTL - W(2p) non ci assicura la divisibilità.

___________________________________________________________________

* Nota

Informo il lettore che per testare i numeri primi di Sophie Germain di norma si usa il seguente teorema.

" Condizione necessaria e sufficiente affinché p = 2q +1  sia primo:  2^{2 q} ≡ 1 (mod 2q+1)   se q è primo "

Questo a sua volta si deduce dal teorema di Lucas:

" Se a^d ≢ 1  (mod n)  per ogni d|(n-1)  ed inoltre a ^n-1  ≡ 1 (mod n)  allora n è primo".

Si sottolinea che i due teoremi, quello famoso di Lucas e quello VTL da me proposto, sfruttano entrambi, ma in modo differente, una proprietà dei numeri primi che consente di distinguere nettamente un numero primo da uno composto. Diversamente accade con il "Piccolo teorema di Fermat", che  sfrutta invece una proprietà valida sia per i numeri primi, sia per infiniti composti, tra i quali quelli di Carmichael.

In questo sito propongo il torema VTL  per renderlo noto, in attesa che se ne possa stabilire: l'originalità, la validità e la praticità.

     Commenti, critiche e correzioni saranno determinanti per continuare o abbandonare questo studio sui polinomi ciclotomici e il conseguente teorema VTL   

Home page

Teoria dei numeri

Teorema VTL - (Wn)_b

Questa pagina è tratta dal libro:  “ N esp1 - Un ordinamento possibile dei numeri primi”

Autore: Vincenzo Vitale   ;   e-mail: vincenzovitale@integernumbers_*org  

ã  L'autore Vincenzo Vitale detiene i diritti esclusivi delle sue opere, non è concesso ad alcuno la loro pubblicazione, neanche parziale.