{"id":2179,"date":"-0001-11-30T00:00:00","date_gmt":"-0001-11-29T23:10:04","guid":{"rendered":""},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T22:00:00","slug":"2179","status":"publish","type":"post","link":"https:\/\/www.vialattea.net\/content\/2179\/","title":{"rendered":"C’\u00e8 una legge matematica che permette di verificare se un numero \u00e8 primo senza dover eseguire tutte le divisioni? Esiste una Regolarit\u00e0 nel succedersi dei numeri primi? Conoscendo un certo numero primo, \u00e8 possibile calcolare il successivo?"},"content":{"rendered":"

I numeri primi sono infiniti. Di questo fatto sono
\n state date varie dimostrazioni.
\nLa prima dimostrazione<\/a> conosciuta \u00e8 dovuta
\n ad Euclide (300 a.C). <\/p>\n

Il pi\u00f9 semplice test di primalit\u00e0<\/i> \u00e8 il
\n noto Crivello di Eratostene<\/b><\/a>,
\n ma al di la del fatto che \u00e8 pi\u00fa semplice del metodo
\n delle divisioni successive, \u00e8 adatto solo per numeri
\n relativamente piccoli. <\/p>\n

Quando i numeri si fanno grandi, occorre
\n utilizzare altri test che per\u00f2 non sono generali. Si
\n applicano cio\u00e8 a particolari forme di numeri (ad esempio
\n i numeri di Mersenne<\/a>), oppure
\n sono validi per numeri non maggiori di un dato massimo.
\n Ad esempio esiste un test di primalit\u00e0 molto migliore
\n che non le divisioni successive o il Crivello di
\n Eratostene, ma vale “solo” per numeri minori di
\n 341550071728321. <\/p>\n

Le dimostrazioni di tali test sono piuttosto
\n complesse, per chi volesse approfondirle esiste una vasta
\n letteratura disponibile ed anche documentazione in
\n rete. <\/p>\n

Il sito pi\u00f9 completo e alla URL: http:\/\/www.utm.edu\/research\/primes\/<\/a>
\n e contiene numerose informazioni e link (in maggioranza
\n in Inglese e di complessit\u00e0 spesso a livello di ricerca)
\n specifici sui numeri primi. <\/p>\n

Per quanto riguarda la regolarit\u00e0 dei numeri
\n primi la risposta \u00e8, in assoluto: No, non esiste alcuna
\n regolarit\u00e0 dei numeri primi. <\/p>\n

Tuttavia, il numero di numeri primi non maggiori
\n di un dato numero x, funzione che \u00e8 chiamata pi(x), ha
\n delle sorprendenti propriet\u00e0: <\/p>\n

Il “teorema dei numeri primi” afferma
\n che: <\/p>\n

                  pi(x)        lim     ---------   = 1        x->inf   x\/(log x)<\/pre>\n
in parole povere x\/(log x) \u00e8 una buona
\n        approssimazione di pi(x).  <\/p>\n
 Da questo teorema (la cui dimostrazione ometto
\n        per piet\u00e0 del lettore) si ricavano due
\n        conseguenze:  <\/p>\n
    \n
  1. l’ ennesimo (n-esimo) numero primo \u00e8,
    \n                all’incirca uguale a: n (log n)<\/li>\n
  2.   
    <\/li>\n
  3. La probabilit\u00e0 che un numero x sia primo \u00e8:
    \n                1\/(log x) <\/li>\n<\/ol>\n
    Queste non sono regolarit\u00e0 di tipo funzionale (ovvero
    \n        non ci consentono di ricavare un numero primo come
    \n        funzione di altri numeri), ma di tipo sostanzialmente
    \n        “statistico”. <\/p>\n
    <\/p>\n
    \n

    \nEsistono infiniti numeri primi<\/a><\/h1>\n
    \n
    Dimostrazione (Euclide, circa 300 A.C.):<\/a><\/h2>\n
    Siano p1<\/sub>,p2<\/sub>,…,pr<\/sub> Tutti i numeri primi<\/p>\n
    minori o uguali a pr<\/sub><\/p>\n
    <\/a><\/p>\n
     sia P = p1<\/sub>p2<\/sub>p3<\/sub>…pr<\/sub><\/p>\n
    + 1 (il prodotto di tutti i numeri primi fino a pr<\/sub>, pi\u00f9<\/p>\n
    uno)<\/p>\n
    <\/a><\/p>\n
     Allora o P \u00e8 a sua volta primo, e si giunge subito alla<\/p>\n
    conclusione sotto riportata, oppure esiste almeno un numero p divisore<\/p>\n
    primo di P. <\/p>\n
    <\/a><\/p>\n
    Se p esiste deve essere diverso da un qualunque pi<\/sub> compreso<\/p>\n
    nell’insieme {p1<\/sub>,p2<\/sub>,…,pr<\/sub>} , altrimenti<\/p>\n
    poich\u00e9 esso \u00e8 fattore sia di P che del prodotto p1<\/sub>p2<\/sub>p3<\/sub>…pr<\/sub><\/p>\n
    deve essere necessariamente fattore anche della loro differenza ossia di:<\/p>\n
    P – p1<\/sub>p2<\/sub>p3<\/sub>….pr<\/sub> = 1; e ci\u00f2<\/p>\n
    \u00e8 impossibile. <\/p>\n
    <\/a><\/p>\n
    \n
    Conclusione:<\/a><\/h3>\n
    Dato un qualunque insieme di tutti i numeri primi fino ad un dato massimo<\/p>\n
    esiste almeno un altro numero primo maggiore del massimo. Di conseguenza<\/p>\n
    il numero di numeri primi \u00e8 infinito.
    \n<\/a><\/p>\n
    ritorna all’inizio<\/a><\/p>\n
    <\/p>\n\n

    <\/a><\/p>\n

    <\/a><\/p>\n<\/div>\n
    Crivello di Eratostene (circa 240 A.C.)<\/a><\/h1>\n
    Algoritmo che consente di individuare tutti i numeri primi minori di un
    \ncerto numero dato. <\/a><\/p>\n
    Supponiamo di voler trovare tutti i numeri primi minori o uguali ad N. <\/a><\/p>\n
    Si inzia scrivendo un elenco dei numeri da 2 ad N.<\/a><\/p>\n
    L’algoritmo procede come segue:
    \n<\/a><\/p>\n
      \n
    1.   Si prende il numero pi\u00f9 piccolo nella lista. Questo \u00e8 un numero primo
      \n      (all’inizio \u00e8 2, ed \u00e8 ovvio che sia primo, ma come vedremo la regola
      \n      continua a valere anche alle successive iterazioni) e fa parte della
      \n      soluzione.<\/a><\/p>\n<\/li>\n
    2.   Si cancella il numero primo trovato e tutti i suoi multipli.<\/a>\n
            Se il numero trovato \u00e8 minore della radice quadrata di N, si torna
      \n      al passo 1)<\/a><\/p>\n<\/p>\n
      \n           altrimenti
      \n<\/a><\/p><\/blockquote>\n
            L’algoritmo \u00e8 terminato. I numeri primi sono tutti quelli trovati,
      \n      pi\u00f9 quelli che rimangono non cancellati nella lista.<\/a><\/li>\n<\/ol>\n
      ritorna all’inizio<\/a><\/p>\n

      \n
      \n<\/a><\/div>\n
      I numeri di Mersenne<\/a><\/h1>\n
      Sono numeri della forma 2N<\/sup>-1 e sono divenuti noti, inizialmente,<\/p>\n
      grazie ad un errore: molti matematici prima del ‘500 ritenevano che tutti<\/p>\n
      i numeri di Mersenne con esponente primo fossero primi. A partire dal ‘500<\/p>\n
      sono stati invece trovati molti numeri di Mersenne ad esponente primo non<\/p>\n
      primi (ad esempio 211<\/sup>-1, 223<\/sup>-1, 229<\/sup>-1). <\/p>\n
      <\/a><\/p>\n
      Tuttavia i numeri di Mersenne rimangono “interessanti”, soprattutto<\/p>\n
      perch\u00e9 esistono test di primalit\u00e0 per numeri di questa forma<\/p>\n
      che hanno reso possibile verificare la primalit\u00e0 di numeri molto<\/p>\n
      grandi. Anzi i numeri primi pi\u00f9 grandi che si conoscono sono tutti<\/p>\n
      numeri di Mersenne, ad esempio \u00e8 stato dimostrato che sono primi<\/p>\n
      i numeri:<\/p>\n
      <\/a><\/p>\n
       2125778<\/sup>-1, 21398269<\/sup>-1 e 22976221<\/sup>-1. <\/p>\n
      <\/a><\/p>\n
      I primi due sono, rispettivamente il 34-esimo e 35-esimo numero primo<\/p>\n
      di Mersenne, mentre il terzo (il pi\u00f9 grande conosciuto alla data<\/p>\n
      del 5 dicembre 1997) \u00e8 candidato al posto di 36-esimo (non \u00e8<\/p>\n
      ancora provato che non ci sia un numero primo di Mersenne maggiore del<\/p>\n
      35-esimo, ma minore di questo). L’ultimo dei tre numeri, se scritto in<\/p>\n
      decimale, avrebbe pi\u00f9 di 895000 cifre. <\/a>
      <\/a><\/p>\n
      ritorna all’inizio<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
      […]<\/p>\n","protected":false},"author":198,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[72],"tags":[],"class_list":["post-2179","post","type-post","status-publish","format-standard","hentry","category-teoria-dei-numeri"],"_links":{"self":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/2179","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/users\/198"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/comments?post=2179"}],"version-history":[{"count":0,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/2179\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/media?parent=2179"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/categories?post=2179"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/tags?post=2179"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}