I numeri della forma b - 1


I test di primalità per i numeri della forma b-1, dove è nota la fattorizzazione di b, ci conducono in un altro ambiente algebrico, non immediatamente visibile.

L'inizio della storia sono le successioni di Fibonacci e di Lucas :

Successioni di Fibonacci e di Lucas
Fissiamo due interi h,k.
La successione di Fibonacci Un(h,k) è così definita:
U0 = 0
U1 = 1
Un = hUn-1 + kUn-2
La successione di Lucas Vn(h,k) è così definita:
V0 = 2
V1 = h
Vn = hVn-1 + kUn-2


Per esempio, con h e k uguali ad 1, {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...} è la successione classica dei numeri di Fibonacci, legata alla crescita dei conigli.

Utilizzando queste successioni otteniamo il nostro secondo criterio di primalità (osserviamo che D = h2 + 4k) :

Criterio di primalità 2

N è primo se e solo se esiste una successione di Fibonacci Un(h,k)
con MCD(kD,N) = 1, tale che:
1) N divide UN+1
2) N non divide U(N+1)/q
per ogni primo q che divide N + 1.

Come nel caso precedente, questo criterio funziona bene per i numeri di una certa forma: ovvero i numeri del tipo b - 1, dove la fattorizzazione di b è nota.

Questa classe di interi comprende i numeri di Mersenne.

Fattoriali diminuiti : n! - 1.
Sono primi per n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, 324, 379, 469, 546, 974, 1963, 3507, 3610 e 6917 (23560 cifre).
Primoriali diminuiti : p# - 1.
In questo caso p è primo e p# è il prodotto di tutti i primi fino a p compreso, per es. 11# = 2 3 5 7 11 = 2310.
Sono primi per p = 3, 5, 11, 13, 41, 89, 317, 337, 991, 1873, 2053, 2377, 4093, 4297, 4583, 6569, 13033, e 15877 (6845 cifre).
Numeri di Mersenne : Fn = 2n - 1
Sono primi per n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, ...
[Indietro|Avanti]