Esiste un metodo per dire che un valore intero N non è primo?

No body ?  No party!!

Beh a pensarci sì; con le frazioni continue e l'espansione periodica è possibile creare un "test di compositezza" ad hoc. Brutto il termine "compositezza", ma l'italiano non offre di meglio perchè invece "compostezza" è un'altra cosa!.

Il risultato di una frazione può dare: 
1 assenza di periodo: numero finito o numero irrazionale  
2 presenza di periodo  
3 presenza di antiperiodo e periodo

Se al denominatore ci sono 2 e 5 o potenze di essi o combinazioni (perché fattori della numerazione per 10), avremo a che fare con un numero finito.

Si definisce gaussiano del numero N rispetto ad una base B, indicato come k = g(N) = T(1/N), “il più piccolo valore k tale che B^k = 1 mod N”.

Si dimostra che il gaussiano k di un rapporto a/b dipende solo dal denominatore b, quindi nel calcolo del gaussiano si può porre a=1 (come nell’algoritmo proposto). Ecco perché spesso è indicato come k = T(1/N).

Un teorema che deriva dal Piccolo Teorema di Fermat porta a dire anche che il gaussiano di n è un divisore della funzione di Eulero φ(n). In particolare se n è primo è φ(n) = n – 1.

Un algoritmo del gaussiano è presentato in APPENDICE.

Primalità? Meglio la compositezza.

Con le frazioni continue e l'espansione periodica in base 10 è possibile creare un "test di compositezza" ad hoc.

E’ brutto il termine "compositezza", ma l'italiano non offre di meglio, anche perché "compostezza" ha un altro significato!.

Teorema (R. Turco)

“Sia n>1 e dispari. Se il quoziente di 1/n ha un gaussiano k = T(1/N) diverso da 1 e (n-1)/T dà un quoziente non intero, allora n non è primo. Se il gaussiano di 1/n equivale a n-1, allora n è primo”.

Esempi

T(1/57)=18   (T diverso da 1)

(57-1)/18=3.1111 non intero

allora 57 è composto.

T(1/3337)=1610   (T diverso da 1)

(3337-1)/1610=2.0720496 etc

allora 3337 è composto.

T(1/3333)=4 con (3333-1)/3=883.0

allora il metodo non può dire se è composto.

T(1/9)=1   violazione della regola   

(9-1)/1=8 intero il metodo non può dire se è composto.

             

T(1/3367)=6 (3367-1)/6  il metodo non può dire se è composto.

T(1/3343)=3342=φ(3343)  è primo!!!

Valutazione del metodo

Se si guarda l’algoritmo isComposite ci si rende conto che, per numeri grandi, già ad esempio per un numero di Mersenne come 2^31-1, poiché il gaussiano è calcolato per successivi incrementi unitari ne consegue che sono necessari molti cicli.

In tal caso è più veloce un algoritmo come isMyPrime o le funzionalità built-in di PARI/GP come eulerphi, isprime, ispseudoprime. Queste ultime funzioni built-in soffrono ovviamente del fatto che dipendono dal numero di primi precaricati e dalla RAM disponibile e allocata al programma.

Alla prox