Teorema 1- Il periodo di un elemento di un gruppo finito divide l'ordine del gruppo.
Questo teorma è del tutto elementare, di natura combinatorica: esprime semplicemente il fatto che i laterali di un sottogruppo formano una partizione del gruppo in parti equipotenti.
Dal Teorema 1 segue immediatamente il famosissimo:
Piccolo Teorema di Fermat (PTF) - Se p è primo e non divide a, allora p divide ap-1 - 1.
Se p è primo, il gruppo moltiplicativo degli interi modulo p è ciclico, possiede cioè un generatore, un elemento di periodo p-1,
Per esempio, modulo 13 le successive potenze di 2 sono {2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1}. Equvalentemente possiamo scrivere : (Z13)* = <2>.
Da questi fatti otteniamo una prima relazione tra periodo e primalità:
N è primo se e solo se nel gruppo moltiplicativo degli interi modulo N esiste un elemento di periodo N - 1.
ed un primo criterio di primalità:
Criterio di primalità 1 - Un intero N è primo se e solo se esiste un a con MCD(a,N) = 1 tale che:
1) N divide aN-1 - 1.
2) Per ogni divisore primo q di N-1
N non divide a(N-1)/q - 1.
Il criterio di primalità 1 è utilissimo quando è nota la fattorizzazione di N - 1. In particolare fornisce subito il:
In questa categoria rientrano i numeri di Fermat:
Numeri di Fermat : Fn = 2(2^n) + 1
Sono primi per n = 0,1,2,3,4.
Per essi a può essere precisato:
Ecco altri interessanti numeri del tipo b + 1, con fattorizzazione di b nota:
Fattoriali aumentati : n! + 1.
Sono primi per n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, 320, 340, 399, 427, 872, 1477 e 6380 (21.507 cifre).