Un'equazione semplice per i numeri Primi

Di Manuela Doglio

Ogni curioso dei numeri Primi, “i mattoni con cui si costruiscono tutti gli altri numeri”, sa che la ricerca di una semplice formula per “distinguere nell'ambito degli interi positivi tutti i numeri Primi e solo essi” è un enigma tuttora irrisolto.
Il libro lo affronta coraggiosamente, esibendo subito una semplice equazione, e mostrando, con dovizia di esempi, che essa è in grado non solo di distinguere i Primi >3 dai Composti, ma anche di generare tutti e solo i numeri Composti e di individuarne i fattori Primi.
Poi ci conduce all’origine dell’equazione, nello strano mondo dei numeri Primi: un insieme molto speciale, che addirittura fa nascere perplessità sull’insieme dei numeri Naturali, e che potrebbe essere all’origine dell’incompletezza (dimostrata dal teorema di Gödel) e dell’indecidibilità (collegata alla Macchina di Turing e alla tesi di Church-Turing) delle teorie formali contenenti l’aritmetica di base.
Le spiegazioni sono trasparenti, alla portata di tutti coloro che hanno nozioni elementari di matematica. Agli esperti il compito di scoprire se c’è qualcosa che non va in questa equazione - o se in essa c’è qualcosa di utile per la soluzione dell’enigma.

• Lingua: Italiano
• Editore: Publisher s14252
• Data di uscita: 29 dic 2018
• ISBN: 9788829584833

Anteprima del libro

Parte

Prima Parte - L'EQUAZIONE

1. L’equazione consente di distinguere i numeri Primi > 3 dai numeri Composti

Un numero Primo è un numero intero positivo che ha due divisori esatti, cioè solo due divisori distinti [1].

Ovvero, un numero Primo è un numero intero positivo maggiore di 1, divisibile (senza resto) soltanto per 1 e per se stesso.

Esempio:

17 è divisibile (senza resto) solo per 1 e per 17.

35 è divisibile (senza resto) per 1, per 35, per 5 e per 7: ha dunque 4 divisori distinti.

Un numero maggiore di 1 che ha più di 2 divisori esatti è detto Composto.

In base al Teorema Fondamentale dell’aritmetica:

Ogni numero Naturale maggiore di 1 o è un numero Primo o si può esprimere come prodotto di numeri Primi. Tale rappresentazione è unica, se si prescinde dall'ordine in cui compaiono i fattori [2].

Esiste una formula che consenta di distinguere i numeri Primi dai numeri Composti? Esiste una funzione che consenta di generare tutti e solo i numeri Primi?

La questione è irrisolta, anche se oggi esistono diversi metodi utili a generare Primi molto grandi e per verificare la primalità di numeri molto grandi [3].

Dato un numero intero positivo, è possibile dire se si tratta di un numero Primo provando a dividerlo per tutti gli interi positivi minori di esso e >1: se in tutte le divisioni risulta un resto, il numero in questione è Primo.

La divisione per tentativi richiede un tempo di calcolo crescente al crescere della grandezza del numero; consente però, se il numero è Composto, di individuarne i fattori Primi.

Esiste un metodo più rapido per sapere se un determinato numero, > 3 e grande a piacere, è Primo, o Composto e, in tal caso, per individuarne i fattori Primi?

La Prima Parte di questo scritto intende fornire una risposta affermativa a questa domanda. Di seguito ne sono indicati i passaggi.

Qualsiasi numero intero positivo dispari >1 si può esprimere come N=2M+3, con M intero >=0. Se M=0, N=3; se M>0, N=2M+3 risulta >3.

Esempi:

M=7; N=2M+3=(2x7)+3=17

M=16; N=2M+3=(2x16)+3=35

Pertanto, dato un qualsiasi numero dispari intero positivo N>1, il relativo valore di M è = (N-3)/2.

Esempi:

N=17; M=(N-3)/2=(17-3)/2=7

N=35; M=(N-3)/2=(35-3)/2=16

Esiste una semplice equazione:

2xy+y+3x=M, x>0, y>=0

che consente di decidere se un numero intero positivo N > 3 è Primo o Composto.

Infatti, se si inserisce nell’equazione il valore di M corrispondente a N (M=(N-3)/2), possono darsi 2 casi:

1. l’equazione non ha soluzioni per valori interi di x>0 e di y>=0: in tal caso N è un numero Primo.

2. l’equazione fornisce una o più soluzioni per valori interi di x>0, e di y>=0: in tal caso N è un numero Composto (e dalle soluzioni si possono ricavare i fattori Primi di N).

Ad esempio, per N=35, M=(35-3)/2=16.

L’equazione 2xy+y+3x=16, con le condizioni x>0, y>=0, ha 2 soluzioni intere:

x=2, y=2; x=3, y=1.

Infatti 35 è un numero Composto, e i suoi fattori Primi sono 5 (=2x+1) e 7(=2y+3).

Se invece assumiamo come condizioni: x>=0, e y>=0 – cioè se ammettiamo che il valore di x possa anche essere = 0 - l’equazione ha SEMPRE almeno una soluzione intera, per qualsiasi valore di M; ma solo per alcuni valori di M l’equazione ha più di una soluzione, e in tali soluzioni x e M sono >0.

Lo si può constatare nella seguente TABELLA 1, dove i casi in cui esiste più di 1 soluzione sono: N=9, 15, 21, 25, 27, 33, 35, 105, 973, 10851.

TABELLA 1

Operando una restrizione delle condizioni, escludendo cioè le soluzioni corrispondenti a M=0 e x=0, e quindi risolvendo:

2xy+y+3x=M, M intero >0, x intero >0, y intero>=0

per diversi valori di M l’equazione non ha alcuna soluzione. Infatti la restrizione elimina dalla TABELLA 1 la colonna corrispondente alla prima soluzione.

L'osservazione chiave è che in tali casi il numero N=2M+3 corrisponde a un numero Primo, come mostra la seguente TABELLA 2.

TABELLA 2

Quanto sopra vale anche se prendiamo un numero grande:

N=3.4691380469033498261731683061749136751396751382777 x 10 ⁴⁹

M=(N-3)/2=17345690234516749130865841530874568375698375691387

Per tale valore di M l’equazione ha 62 soluzioni intere per x>0, y>=0.

N infatti è un numero Composto, e ha 6 fattori Primi: 41, 1097, 44273, 822901, 1716241, 12335770570090359523265185157.

Dunque l’analisi delle soluzioni dell'equazione fornisce un metodo efficace per distinguere se un numero intero positivo dispari >3 è Primo o Composto: se l'equazione 2xy+y+3x=M, con le condizioni x>0, y>=0, non ha soluzioni intere, il numero N corrispondente a M è Primo; se invece l'equazione ha soluzioni intere, N è Composto [4] .

Infatti, a controprova, inserendo nell’equazione 2xy+y+3x=M valori interi qualsiasi di x>0 e di y>=0, i valori di M che si generano corrispondono sempre e soltanto a numeri interi dispari Composti N=2M+3 >=9; e, al crescere dei valori di x e y, si generano progressivamente i valori di M corrispondenti a tutti i numeri interi dispari Composti.

La seguente TABELLA 3 mostra alcuni esempi.

TABELLA 3

[1] Per questa definizione si veda http://matematica-old.unibocconi.it/LangZac/zaccagnini.pdf.

[2] Per seguire più agevolmente lo scritto, o per chi voglia fare qualche verifica, può essere utile l’elenco dei numeri Primi <1000:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.

Per un elenco dei numeri Primi <10000 si veda ad esempio: https://www.youmath.it/images/stories/algebra-medie/Numeri-primi-da-1-a-10000.pdf.

Elenchi molto più estesi si trovano in https://primes.utm.edu/.

[3] Alla voce di Wikipedia: https://it.wikipedia.org/wiki/Formula_per_i_numeri_primi si trova una chiara e ampia illustrazione del problema, che è sinteticamente espresso nelle prime righe: Una formula per i numeri primi è un'espressione che consenta di distinguere nell'ambito degli interi positivi tutti i numeri primi e solo essi. La ricerca di una tale formula è da secoli l'obiettivo di tanti studiosi, sia professionisti che dilettanti, e finora non è nota alcuna formula semplice di questo tipo. Per contro negli ultimi decenni lo studio dei numeri primi si è servito sempre più sistematicamente di attività sperimentali condotte con il computer.

Il sito più completo