"METODO", N. 19/2003

Nota di rettifica al Teorema 14

Si rende noto che, in seguito a segnalazione di un visitatore molto attento e preparato – il Prof. Giuseppe Guarino di Potenza – il test di primalità:

(2^n-2)/ n=k intero se n è primo

non è valido per 22 numeri (su 1228 numeri primi fino a 10.000) e precisamente:

341, 561, 645, 1105, 138, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, e 8911

individuati dal Prof. Guarino con un suo algoritmo scritto in linguaggio MAPLE.
Per rimediare a questo inconveniente, suggeriamo di sottoporre il numero da verificare se è primo o meno, al nostro test, e se lo supera, pure all’algoritmo del Prof. Guarino: se li supera entrambi (dà k intero nel primo e non figura tra i numeri con k intero ma tuttavia non primi dati dall’algoritmo), allora il numero testato è primo.
Ma ulteriori algoritmi, presumibilmente più efficienti, e basati su un altro noto test di primalità: [(n-1)!+1]/n = k intero se n è primo, collegato al nostro Teorema n° 1, sono allo studio, e dovrebbero dare automaticamente e rispettivamente tutti i numeri primi di forma 6n-1 e 6n+1, tranne il 2 e il 3.

Gruppo Eratostene – Caltanissetta

Francesco Di Noto – Anna Rita Tulumello
(Gruppo Eratostene – Caltanissetta)
TEOREMA N° 14:
NUOVO TEST DI PRIMALITÀ

Un numero n è primo se e solo se (2ⁿ-2)/n=k intero (k decimale in caso contrario).

DIMOSTRAZIONE

Nel triangolo di Tartaglia, i termini di ogni riga che partono da un qualsiasi numero primo n, sono divisibili per n; cioè, se

Questo avviene perché, solo in questi casi, nel calcolo dei coefficienti rinominali

=

n, essendo primo, non è semplificabile con i denominatori; per cui "costringe" tutti i coefficienti ad essere divisibili, e quindi multipli, di n stesso.
Mentre ciò non succede se n è composto, perché è riducibile, e il risultato finale può non essere, almeno una volta, divisibile per n; in tal caso il risultato di è decimale, e questo rende decimale anche la somma di tutti i coefficienti binominali.
Tale somma, per ogni n^esima riga, è, come si sa, 2ⁿ, comprese le due unità estreme; che non sono divisibili per nessun numero, oltre che per 1; e quindi togliendo queste due unità da 2ⁿ, e dividendo per n, si ha un numero intero k solo se n è primo, a causa di quanto sopra

intero con k=Sk_i somma di tutti i risultati interi parziali escluse le unità estreme.
Facciamo alcuni esempi:
per n=9, nona riga; 9=3²= composto ;

=

(9•8)/(1•2)= 36; 36/9=4 k intero

perché il 9 in questo caso non è stato ridotto con un denominatore 3, perché assente; ma:

=(9•8•7)/(1•2•3)=3•4•7=84; 84/9=9,3;

ora k è decimale perché 9 è stato ridotto col 3 a denominatore, e poiché il 9 non risulta più al numeratore, né intero né come prodotto, il risultato di

non è intero; infatti è 9, ; cioè k decimale, per cui 9 è composto.
Per n=11 primo, abbiamo invece:

a)

b)

c)

d)

e)

f)

Da qui in poi i valori sono simmetrici rispetto alla prima metà della 11ª riga del triangolo di Tartaglia, per cui anche tutti i relativi valori di k_i, uguali a quelli della prima metà riga, sono interi.
Per cui lo è anche la somma totale di tutti i k_i=1+5+15+30+42+30+15+5+1=186, che è poi il risultato equivalente della:

Così è per tutti i numeri primi, per cui riteniamo dimostrato questo nuovo testo di primalità:

Esempi per i più piccoli numeri primi e composti:

e così via; per esempio, anche usando un coefficiente binominale; purchè, per n composto, uno dei fattori sia al denominatore:

quindi 25 non è primo, infatti 25=5×5

35 non è primo infatti 35=5×7
Mentre:

anche questo intero, come pure tutti i coefficienti interi, che determinano la primalità di 37, come pure di conseguenza la regola generale:

TABELLA PER I PRIMI 25 n